中文题目
解题
利用前缀和和差分
参考:https://www.cnblogs.com/wkfvawl/p/9762574.html
#include <iostream>
using namespace std;
//Karen and Coffee
const int N = 200000 + 10;
int a[N],s[N],sum[N];
int main() {
int n,k,q;
cin >> n >> k >> q;
for(int i = 1;i<=n;i++) {
//先求差分数组,求l--r这个区间的差分数组,+=1表示这个区间的加1,-=1表示这个区间的减1
int l,r;
cin >> l >> r;
s[l] += 1;
s[r + 1] -= 1;
}
for(int i = 1;i<=N;i++) {
//利用差分数组求原数组,就能知道哪个温度满足k种菜谱了
a[i] = s[i] + a[i - 1];
if(a[i] >= k) {
sum[i]+=1; //给sum[i] + 1,表示可接受的温度
}
}
for(int i = 1;i<=N;i++) {
sum[i] += sum[i - 1]; //求前缀和,方便后面求Karen问的问题中,温度为l -- r这个区间的满足“可接受”的温度的有多少个
}
for(int i = 0;i<q;i++) {
int l,r;
cin >> l >> r;
cout << sum[r] - sum[l - 1] << endl;
}
// for(int i = 1;i<=100;i++) {
// cout << "i: " << i << ":" << a[i] << endl;
// }
/* Time Exceed */
// for(int i = 1;i<=q;i++) {
// int l,r;
// cin >> l >> r;
// int ans = 0;
// for(int i = l;i<=r;i++) {
// if(a[i] >= k){
// ans++;
// }
// }
// cout << ans << endl;
// }
}