題目描述

Karen 喜歡咖啡。
她有?n?本食譜，第?ii?本食譜包含兩個數?l[i],r[i]，表示這本食譜推薦用 [l[i],r[i]]之間的溫度（包含?l_i.r_ili?.ri?）來煮咖啡。
Karen 認為一個溫度?aa?是可接受的當且僅當有?\ge k≥k?本食譜推薦用?aa?來煮咖啡。
Karen 有?kq?個問題，每個問題用一對正整數?a_i,b_iai?,bi??來表示，表示她問?[a_i,b_i][ai?,bi?]?之間有多少個溫度是可接受的。

輸入格式

第一行包含3個整數n,k,q，其中1<=k<=n<=200000,1<=q<=200000。

接下來的n行，每行包含2個整數l和r，其中1<=l<=r<=200000。

再接下來有q行，每行包含2個整數a和b，其中1<=a<=b<=200000。

輸出格式

共q行，每行一個整數，表示可接受溫度的個數。

樣例輸入

3 2 4 91 94 92 97 97 99 92 94 93 97 95 96 90 100

樣例輸出

3 3 0 4

樣例輸入

2 1 1 1 1 200000 200000 90 100

樣例輸出

0

問題提示

此題可用差分+前綴和實現。

思路：

1.根據食譜推薦溫度，每個溫度推薦食譜數量+1(差分)

? ? 統計每個溫度推薦的食譜數量

2.統計區間內可接受的溫度數量

? ? ? ? ? 1.判斷該溫度是否接受 1

? ? ? ? ? 2.不可接受 0

? ? ? ? ? 3.利用前綴和統計總數

于是問題就解決了

接下來上代碼！

#include <iostream> using namespace std; #define int long long #define F(i,a,b) for(int i=(a);i<=(b);i++) #define R(i,a,b) for(int i=(a);i>=(b);i--) const int N=200005; int n,k,m,l,r,sum=0; int a[N],s[N];//a[N]為某溫度推薦的食譜數量，s[N]為前i溫度可接受溫度的總數 signed main() {//讀入數據 scanf("%lld%lld%lld",&n,&k,&m);F(i,1,n){//讀入數據 scanf("%lld%lld",&l,&r);//差分，根據食譜推薦溫度，每個溫度推薦食譜數量+1 a[l]++;a[r+1]--;}//前綴和求解修改后的內容F(i,1,N-5) a[i]+=a[i-1];F(i,1,N-5){//如果溫度可接受，可接受溫度數量加一 if(a[i]>=k) s[i]=s[i-1]+1;//如果不可接受，繼承上一可接受溫度數量 else s[i]=s[i-1];}F(i,1,m){//讀入數據 cin>>l>>r;//利用前綴和求出區間內可接受溫度 cout<<s[r]-s[l-1]<<"\n";}return 0; }

總結

以上是生活随笔為你收集整理的180418 Karen and Coffee 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。