本题链接：CSP 202203-2 出行计划
本博客给出本题截图：
题解
比如上图中，q 就落在了三个区间中，故输出 3 ，为此考虑到【前缀和、差分】，关于这两个算法的思想和解释见博客：前缀和、差分
再次强调，这两个算法可以说是第二题的必考算法，读者请务必掌握
C++
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 200010; int s[N]; int main() { int n, m, k; cin >> n >> m >> k; // 差分 for (int i = 1; i <= n; i ++ ) { int t, c; cin >> t >> c; // 差分和前缀和数组要从 1 开始，否则无意义 s[max(1, t - k - c + 1)] ++, s[max(1, t - k + 1)] --; } // 注意这里在计算前缀和的时候，for 循环时循环到 N 而不是 n for (int i = 1; i <= N; i ++ ) s[i] += s[i - 1]; for (int i = 1; i <= m; i ++ ) { int q; cin >> q; cout << s[q] << endl; } return 0; }
