【AtCoder】离线询问+树状数组

D - AtCoder Express 2

题目描述

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

---

题意

给定 $n(\le 500)$，$m(\le 2e5)$，$q(\le 1e5)$，然后输入 $m$ 个在 $[1,n]$ 内的闭区间 $[L,R]$。
接下来输入 $q$ 个询问，每个询问输入两个数表示闭区间 $[i,j]$，对每个询问输出在 $[i,j]$ 内的完整闭区间个数。

思路

如本文标题，我们需要对询问离线处理，这样对于区间询问，我们就可以进行排序，并使得左端点单调增，以便处理后续问题。

考虑用树状数组维护区间右端点，所以可以先将所有的区间的右端点加入树状数组中。在每次询问一个区间 $[l,r]$ 时，删掉所有区间左端点小于 $l$ 的树状数组中右端点的值。然后直接进行查询当前右端点小于等于 $r$ 的值的个数，即位该询问的结果。

代码

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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49