CSP-202203-2-出行计划
关键点：前缀和数组（高频考点）
详见：【CSP考点回顾】前缀和数组
解题思路
解法利用差分数组技巧，使得更新时间区间的操作和查询操作的时间复杂度都是 O(1)，整体算法的时间复杂度主要由遍历出行计划和查询决定，即 O(n + m)。
-
初始化一个数组
diffArr用于记录时间点的变化，这个数组的大小设定为能包含所有可能的时间点（根据问题限制，时间点不会超过 200,005）。 -
遍历所有 n 个出行计划，对于每个计划，计算出它有效的时间区间 [x, y]，即从 ti - k - ci + 1 到 ti - k。如果计算出的 y < 1，则忽略该出行计划，因为它不可能在任何查询时间内有效。
-
（重点） 使用差分数组的技巧来处理时间区间的更新。如果一个出行计划在时间区间 [x, y] 内有效，那么在 diffArr 数组中，位置 x 的值增加 1（表示从时间 x 开始，出行计划数增加），而位置 y+1 的值减少 1（表示从时间 y+1 开始，出行计划数减少）。这是因为在差分数组中，一个区间的开始位置加 1，结束位置的下一个减 1，可以用来反映这一区间内的数量变化。
-
在更新完所有出行计划后，遍历 diffArr 数组计算其前缀和，这将转换 diffArr 数组成为一个在每个时间点具体有多少出行计划活跃的数组。
-
对于每个查询时间 q，直接输出 diffArr[q] 的值，这就是在时间点 q 活跃的出行计划总数。
完整代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k, ti, ci, q, diffArr[200005];
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
{
cin >> ti >> ci;
int x = ti - k - ci + 1, y = ti - k; // 符合条件的时间区间 [x, y]
if (y < 1) continue; // y < 1直接跳过（肯定没有任何一个出行符合条件）
else
{
x = max(1, x); // x至少为1（规定从1开始）
diffArr[y + 1]--, diffArr[x]++; // 在x处加1，y+1处减1，用差分数组记录每个时间点的变化
}
}
for (int i = 1; i < 200005; i++)
{
diffArr[i] += diffArr[i - 1]; // 差分数组计算前缀和
}
for (int i = 0; i < m; i++) // 处理查询
{
cin >> q;
cout << diffArr[q] << endl; // 满足条件的出行计划总数
}
return 0;
}
