AcWing 4455. 出行计划
原题链接
简单
差分+前缀和
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 3e5 + 10;
int n, m, k;
PII interval[N];
int s[M];
int main() {
scanf("%d%d%d", &n, &m, &k);
int a, b;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
interval[i] = {max(0, a - b + 1), a};
}
// 差分
for (int i = 1; i <= n; i++) {
int l = interval[i].x, r = interval[i].y; // 对l~r上的所有元素值+1
s[l] += 1;
s[r + 1] -= 1;
}
// 构造前缀和数组
for (int i = 1; i < M; i++) s[i] += s[i - 1];
int t;
while (m--) {
scanf("%d", &t);
t += k;
printf("%d\n", s[t]);
}
return 0;
}