前缀和与差分

例题：CSP 出行计划

• 实际上是求，对于所有区间$[1-c_i+t_i+k, t_i-k]$和当前给定的q，q落在多少个区间
• 那么可以每次获取$c_i$和$t_i$时，统计这个区间数字出现次数，即让s[区间]++
• 涉及到区间同一增减，可以用差分，注意越界问题

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;
int s[N];

int main()
{
    int n,m,k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
    {
        int t, c;
        scanf("%d%d", &t, &c);
        //[1 - ci + ti - k, ti - k]区间都加上1
        s[max(1, 1-c+t-k)]++, s[max(1, t-k+1)]--;
    }

    for (int i = 1; i <= N; i ++ )
        s[i] += s[i-1];

    while (m -- )
    {
        int q;
        scanf("%d", &q);
        cout << s[q] << endl;
    }

    return 0;
}