1400*B. Karen and Coffee

Examples

input

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

output

3
3
0
4

input

2 1 1
1 1
200000 200000
90 100

output

0

 解析：

        题意为，给你多个区间（会有重叠），每个区间的每个值都会为这个值累加 1。再给一些查询区间，问这个区间有多少个数满足，其累加值大于k。

        数据量2e5，为O（NlogN）的复杂度。

        两重遍历肯定超时，所以要把单次查询的复杂度降低为 logN，所以可以树状数组。

        开始差分记录每个点的累加值，遍历将大于累加值大于等于 k，的点放入树状数组，然后每次查询直接 logN 获取查询区间的满足题意的个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,k,q,a[N],c[N],x,y,p[N];
int lowbit(int x){return x&-x;
}
void add(int x){for(int i=x;i<=2e5;i+=lowbit(i)) p[i]+=1;
}
int sum(int x,int k){int ans=0;for(int i=y;i;i-=lowbit(i)) ans+=p[i];for(int i=x-1;i;i-=lowbit(i)) ans-=p[i];return ans;
}
int main(){scanf("%d%d%d",&n,&k,&q);for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);c[x]+=1;	//差分统计每个区间的增加 c[y+1]-=1;}for(int i=1;i<=2e5;i++){a[i]=a[i-1]+c[i];if(a[i]>=k) add(i);		//如果某个点的累计数大于 k，则加入树状数组 }while(q--){scanf("%d%d",&x,&y);printf("%d\n",sum(x,y));	//查询 }return 0;
}