问题描述
最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。
具体来时，如果在 t 时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要 k 个单位时间，即在 t+k 时刻可以获得结果。如果一个场所要求持 24 个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第 t+k 时刻到第 t+k+23 时刻进入该场所。
小 C 按时间顺序列出接下来的 n 项出行计划，其中第 i 项（1≤i≤n）可以概括为：
ti 时刻进入某场所，该场所需持有 ci 个单位时间内的核酸检测结果入内，其中 0<ci≤2×105。
为了合理安排核酸检测时间，试根据小 C 的出行计划，回答如下查询：
- 如果在 q 时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？
这样的查询共有 m 个，分别为 q1,q2,⋯,qm；查询之间互不影响。
输入格式
输入的第一行包含空格分隔的三个正整数 n、m 和 k，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。
接下来输入 n 行，其中每行包含用空格分隔的两个正整数 ti、ci，表示一项出行计划；出行计划按时间顺序给出，满足 0<t1≤t2≤⋯≤tn≤2×105。
最后输入 m 行，每行仅包含一个正整数 qi，表示一个查询。m 个查询亦按照时间顺序给出，满足 0<q1<q2<⋯<qm≤2×105。
输出格式
输出共 m 行，每行一个整数，表示对应查询的答案。
样例输入
6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2样例输出
3
3样例解释
时刻 1 做检测，可以满足第三、四、六项出行计划；
时刻 2 做检测，可以满足第四、五、六项出行计划。
子任务
40% 的测试数据满足 0<n,k≤1000、m=1；
70% 的测试数据满足 0<n,m,k≤1000；
全部的测试数据满足 0<n,m,k≤10^5。
题目分析
根据题意，就是根据给定的核酸检测时刻q和出核酸结果所需时间段k,以及所到达的场所检测结果有效时间c,可以确定出来核酸结果有效的持续区间。如果对应的场所t恰好在有效持续区间内，那么可以进入该场所。按照这种思路写下来的代码只能得70分，剩下的30分因为数据量太大超时了。
所以需要换另外一种思路去解题，上面一种思路是去判断t是否在核酸有效区间[q+k,q+c+k-1]中，这样的判断嵌套了两个for循环比较耗费时间，我们不妨换成去判断每一个q覆盖了多少个有效区间，即q必须覆盖在[t-c-k+1,t-k]区间中才有效。
涉及到对区间内数进行加减，就可以利用差分前缀和思想：对于每一个场所的[t-c-k+1,t-k]区间之内的所有数加1，代表这个区间内所有数都被覆盖了一次。差分完成后算出来原来数组值，就用到前缀和。最后判断每一个q看看有多少个区间覆盖过，只用了一个for循环就能解决，降低了时间复杂度。下面附上超时的和满分代码：
超时的70分代码
#include<iostream>
#include<cmath>
using namespace std;
int n,m,k,q;
int a1[100001],a2[100001];
int check(int s){
int cnt=0;
for(int i=0;i<n;i++){
if(a1[i]<=(q+a2[i]+k-1)&&a1[i]>=(q+k))
cnt++;
}
return cnt;
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++){
cin>>a1[i]>>a2[i];
}
for(int i=0;i<m;i++){
cin>>q;
cout<<check(q)<<endl;
}
return 0;
}满分代码
#include<iostream>
#include<cmath>
#define N 200001
using namespace std;
int n,m,k,q,t,c;
int a[N];
int main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++){
cin>>t>>c;
a[max(t-c-k+1,0)]++;//差分，由于q的取值>0所以区间最小取0。
a[max(t-k+1,0)]--;
}
for(int j=1;j<N;j++){//前缀和
a[j]+=a[j-1];
}
for(int i=0;i<m;i++){
cin>>q;
cout<<a[q]<<endl;
}
return 0;
}