题目描述
input#1：
2 3 1
1 1
1 2
2 2
1 2
output#1：
3
input#2：
10 3 2
1 5
2 8
7 10
1 7
3 10
output#2：
1
1
input#3：
10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10
output#3：
7
9
10
6
8
9
6
7
8
10
题意
思路
如本文标题，我们需要对询问离线处理，这样对于区间询问，我们就可以进行排序，并使得左端点单调增，以便处理后续问题。
考虑用树状数组维护区间右端点，所以可以先将所有的区间的右端点加入树状数组中。在每次询问一个区间 [ l , r ] [l, r][l,r] 时，删掉所有区间左端点小于 l ll 的树状数组中右端点的值。然后直接进行查询当前右端点小于等于 r rr 的值的个数，即位该询问的结果。
代码
class BIT { public: BIT() { memset(tr, 0, sizeof tr); } int tr[N]; void add(int x, int v = 1) { for (; x < N; x += x & -x) tr[x] += v; } int sum(int x) { int res = 0; for (; x; x -= x & -x) res += tr[x]; return res; } }; int n, m, q; struct node { int l, r; int id; bool operator<(const node &A) const { if (l == A.l) return r < A.r; return l < A.l; } }; node a[N], b[N]; int res[N]; void solve() { cin >> n >> m >> q; BIT tree; for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; a[i] = {l, r}; tree.add(r, 1); } for (int i = 1; i <= q; i++) { int l, r; cin >> l >> r; b[i] = {l, r, i}; } sort(a + 1, a + 1 + m); sort(b + 1, b + 1 + q); int j = 1; for (int i = 1; i <= q; i++) { int l = b[i].l, r = b[i].r, id = b[i].id; while (j <= m && a[j].l < l) { tree.add(a[j].r, -1); j++; } res[id] = tree.sum(r); } for (int i = 1; i <= q; i++) { cout << res[i] << endl; } }
