出行计划（2023寒假每日一题 16）

最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。

具体来时，如果在 $t$ 时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。

这里我们假定等待核酸检测结果需要 $k$ 个单位时间，即在 $t+k$ 时刻可以获得结果。

如果一个场所要求持 $24$ 个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第 $t+k$ 时刻到第 $t+k+23$ 时刻进入该场所。

小 $C$ 按时间顺序列出接下来的 $n$ 项出行计划，其中第 $i$ 项（$1\le i\le n$）可以概括为：$t_i$ 时刻进入某场所，该场所需持有 $c_i$ 个单位时间内的核酸检测结果入内，其中 $0<c_i\le 2\times 10^5$ 。

为了合理安排核酸检测时间，试根据小 $C$ 的出行计划，回答如下查询：

如果在 $q$ 时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足这样的查询共有 $m$ 个，分别为 $q_1,q_2,\cdots ,q_m$ ；查询之间互不影响。

输入格式
输入的第一行包含空格分隔的三个正整数 $n$ 、$m$ 和 $k$ ，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。

接下来输入 $n$ 行，其中每行包含用空格分隔的两个正整数 $t_i$ 、$c_i$ ，表示一项出行计划；出行计划按时间顺序给出，满足 $0<t_1\le t_2\le \cdots \le t_n\le 2\times 10^5$ 。

最后输入 $m$ 行，每行仅包含一个正整数 qi ，表示一个查询。$m$ 个查询亦按照时间顺序给出，满足 $0<q^1<q^2<\cdots <q^m\le 2\times 10^5$ 。

输出格式
输出共 $m$ 行，每行一个整数，表示对应查询的答案。

数据范围
$40\%$ 的测试数据满足 $0<n,k\le 1000、m=1$；
$70\%$ 的测试数据满足 $0<n,m,k\le 1000$；
全部的测试数据满足 $0<n,m,k\le 10^5$。

输入样例：

6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2
1
2
3
4
5
6
7
8
9

输出样例：

3
3
1
2

样例解释
时刻 $1$ 做检测，可以满足第三、四、六项出行计划；
时刻 $2$ 做检测，可以满足第四、五、六项出行计划。

---

思路：

对于某个场所只有当出行时刻满足：$q+k<=t_i<=q+k+c_i-1$ 时，这些出行时刻才会算数，这个式子可以转换为 $t_i-c_i-k+1<=q<=t_i-k$，即可以看作对每个 $q$ 求有多少个 $i$ 满足这个性质，转换为对于当前 $q$，求它覆盖了多少个这样的区间，用差分可以解决。

#include

using namespace std;

const int N = 200010;

int d[N];

int main(){
    
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    
    int t, c;
    for(int i = 0; i < n; i++){
        scanf("%d%d", &t, &c);
        int l = t-c-k+1, r = t-k;
        if(r > 0) d[max(l, 0)]++, d[r+1]--;
    }
    for(int i = 1; i < N; i++) d[i] += d[i-1];
    int q;
    for(int i = 0; i < m; i++){
        scanf("%d", &q);
        printf("%d\n", d[q]);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28