题目描述
算法
(二维前缀和) $O(N^2 + M + Q)$
我们可以将每个火车抽象为一个点,然后预计算到位置 $i$ 为止前面有多少个点。
注意到这里的 $N$ 最大只有 $500$,所以我们可以用二维前缀和来处理。
红色区域内点的数量按如下方式计算:
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<int> l(m), r(m);
rep(i, m) cin >> l[i] >> r[i];
vector s(n + 1, vector<int>(n + 1));
rep(i, m) s[l[i]][r[i]]++;
rep(i, n + 1)rep(j, n) s[i][j + 1] += s[i][j];
rep(i, n)rep(j, n + 1) s[i + 1][j] += s[i][j];
rep(qi, q) {
int l, r;
cin >> l >> r;
--l;
int ans = s[r][r];
ans -= s[l][r];
ans -= s[r][l];
ans += s[l][l];
cout << ans << '\n';
}
return 0;
}
^v^