目录
按时间分治
不多说了，直接看题吧。
题目大意
有 $n$ 个时间点，每个时间点都有某个数 $x$ 出现或消失，对于每个时间点，求当前数的子集最大异或和。
思路分析
可以把问题看作每个数都有一个出现时间和消失时间。考虑对时间建线段树，每个结点是一个 std::vector。然后对于每一个元素，我们在线段树上将它对应的区间 push_back 进这个元素。最后回答询问的时候，我们将线段树 DFS 一遍，求出每个结点到根上的所有数的线性基即可。时间复杂度 $O(n \log n)$。
其实这个做法运用的思想就是对时间进行分治。
代码实现
1 | |
2 | |
3 | |
4 | |
5 | using namespace std; |
6 | |
7 | const int maxn = 5e5, maxm = 1 << 20, logn = 31, logm = 20; |
8 | int n, a[maxn + 3], b[logm + 3][logn + 3], ans[maxn + 3]; |
9 | map<int, int> mp; |
10 | vector<int> seg[maxm + 3]; |
11 | |
12 | void modify(int rt, int l, int r, int lx, int rx, int x) { |
13 | if (l >= lx && r <= rx) { |
14 | seg[rt].push_back(x); |
15 | return; |
16 | } |
17 | if (lx <= mid) { |
18 | modify(ls, l, mid, lx, rx, x); |
19 | } |
20 | if (rx > mid) { |
21 | modify(rs, mid + 1, r, lx, rx, x); |
22 | } |
23 | } |
24 | |
25 | void insert(int b[], int x) { |
26 | for (int i = logn - 1; ~i; i--) { |
27 | if (x >> i & 1) { |
28 | if (!b[i]) { |
29 | b[i] = x; |
30 | break; |
31 | } |
32 | x ^= b[i]; |
33 | } |
34 | } |
35 | } |
36 | |
37 | int query(int b[]) { |
38 | int x = 0; |
39 | for (int i = logn - 1; ~i; i--) { |
40 | x = max(x, x ^ b[i]); |
41 | } |
42 | return x; |
43 | } |
44 | |
45 | void solve(int rt, int l, int r, int dep = 1) { |
46 | for (int i = 0; i < seg[rt].size(); i++) { |
47 | insert(b[dep], seg[rt][i]); |
48 | } |
49 | if (l == r) { |
50 | ans[l] = query(b[dep]); |
51 | return; |
52 | } |
53 | memcpy(b[dep + 1], b[dep], sizeof(b[dep])); |
54 | solve(ls, l, mid, dep + 1); |
55 | memcpy(b[dep + 1], b[dep], sizeof(b[dep])); |
56 | solve(rs, mid + 1, r, dep + 1); |
57 | } |
58 | |
59 | int main() { |
60 | scanf("%d", &n); |
61 | for (int i = 1; i <= n; i++) { |
62 | scanf("%d", &a[i]); |
63 | if (a[i] > 0) { |
64 | mp[a[i]] = i; |
65 | } else { |
66 | a[i] = -a[i]; |
67 | modify(1, 1, n, mp[a[i]], i - 1, a[i]); |
68 | mp[a[i]] = 0; |
69 | } |
70 | } |
71 | for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) { |
72 | if (it -> second) { |
73 | modify(1, 1, n, it -> second, n, it -> first); |
74 | } |
75 | } |
76 | solve(1, 1, n); |
77 | for (int i = 1; i <= n; i++) { |
78 | printf("%d\n", ans[i]); |
79 | } |
80 | return 0; |
81 | } |
CDQ 分治
CDQ 分治是一类特殊的分治，指的是在分治过程中计算左半部分对右半部分产生的贡献。
偏序问题是 CDQ 分治的经典例题。
题目大意
有 $n$ 次操作，分为两种：
1 x y z添加一颗坐标为 $(x, y, z)$ 的星星。2 lx ly lz rx ry rz询问以 $(lx, ly, lz)$ 为左下角，$(rx, ry, rz)$ 为右上角的长方体内有多少星星。
数据范围：$n \le 5 \times 10^4$。
思路分析
这题的本质是四维偏序问题（前三维是显然的，另一维是时间），可以使用两次 CDQ 分治 + 树状数组解决（当然你也可以写树套树套树）。
先将每个长方体询问转化成 $8$ 个前缀询问，这样我们只需考虑在某个前缀询问之前，三维坐标都不大于它的星星个数。我们可以把每个操作看作一个五元组 $(i, x, y, z, \text{type})$，$i$ 表示操作的标号，$(x, y, z)$ 表示坐标，$\text{type}$ 表示操作类型。
我们对操作的标号 $i$ 做一遍分治。假设一次分治时左端点是 $l$，右端点是 $r$。我们令 $\text{mid} = \lfloor \frac{l + r}{2} \rfloor$，那么我们只考虑 $i \le \text{mid}$ 的修改对 $i > \text{mid}$ 询问的贡献。这样做完后，我们发现对于每个询问，它之前的修改都恰好对它自己做了一次贡献，也就是答案的计算不重复也不遗漏。这样分治以后，总共的时间复杂度多了一个 $\log$，但是问题的维数减少了一。
将 $i$ 这一维去掉以后，问题就变成了对于每个询问，求三维坐标都不大于它的星星个数，不用再考虑星星和询问的相对位置了。之后，我们用同样的方法去掉 $x$，这样问题就从三维降到了二维。对于二维的问题，我们将二元组按照第一维排序，然后使用树状数组计算答案即可。总共的复杂度为 $O(n\log^3 n)$。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 4e5; |
5 | int T, Q, n, m, q, sz, tmp[maxn + 3], ans[maxn + 3], bit[maxn + 3]; |
6 | bool bel[maxn + 3], tb[maxn + 3]; |
7 | |
8 | struct event { |
9 | int type, x, y, z; |
10 | event(int type = 0, int x = 0, int y = 0, int z = 0): type(type), x(x), y(y), z(z) {} |
11 | } eve[maxn + 3], cur[maxn + 3], mrg[maxn + 3]; |
12 | |
13 | void add_event(int type, int x, int y, int z) { |
14 | n++, eve[n] = event(type, x, y, z); |
15 | } |
16 | |
17 | void add(int x, int y) { |
18 | for (int i = x; i <= sz; i += i & -i) { |
19 | bit[i] += y; |
20 | } |
21 | } |
22 | |
23 | int sum(int x) { |
24 | int y = 0; |
25 | for (int i = x; i; i ^= i & -i) { |
26 | y += bit[i]; |
27 | } |
28 | return y; |
29 | } |
30 | |
31 | void solve(int l, int r) { |
32 | if (l == r) { |
33 | return; |
34 | } |
35 | int mid = (l + r) / 2; |
36 | solve(l, mid); |
37 | solve(mid + 1, r); |
38 | int p = l, q = mid + 1, cnt = 0; |
39 | while (p <= mid || q <= r) { |
40 | if (q > r || (p <= mid && cur[p].y <= cur[q].y)) { |
41 | if (bel[p] == false && !cur[p].type) { |
42 | add(cur[p].z, 1); |
43 | } |
44 | tb[++cnt] = bel[p]; |
45 | mrg[cnt] = cur[p++]; |
46 | } else { |
47 | if (bel[q] == true && cur[q].type) { |
48 | int x = cur[q].type > 0 ? cur[q].type : -cur[q].type, y = cur[q].type > 0 ? 1 : -1; |
49 | ans[x] += y * sum(cur[q].z); |
50 | } |
51 | tb[++cnt] = bel[q]; |
52 | mrg[cnt] = cur[q++]; |
53 | } |
54 | } |
55 | for (int i = l; i <= mid; i++) { |
56 | if (bel[i] == false && !cur[i].type) { |
57 | add(cur[i].z, -1); |
58 | } |
59 | } |
60 | for (int i = l; i <= r; i++) { |
61 | bel[i] = tb[i - l + 1]; |
62 | cur[i] = mrg[i - l + 1]; |
63 | } |
64 | } |
65 | |
66 | void cdq(int l, int r) { |
67 | if (l == r) { |
68 | return; |
69 | } |
70 | int mid = (l + r) / 2; |
71 | cdq(l, mid); |
72 | cdq(mid + 1, r); |
73 | int p = l, q = mid + 1; |
74 | m = 0; |
75 | while (p <= mid || q <= r) { |
76 | if (q > r || (p <= mid && eve[p].x <= eve[q].x)) { |
77 | cur[++m] = eve[p++], bel[m] = false; |
78 | } else { |
79 | cur[++m] = eve[q++], bel[m] = true; |
80 | } |
81 | } |
82 | for (int i = l; i <= r; i++) { |
83 | eve[i] = cur[i - l + 1]; |
84 | } |
85 | solve(1, m); |
86 | } |
87 | |
88 | int main() { |
89 | scanf("%d", &T); |
90 | while (T--) { |
91 | for (int i = 1; i <= q; i++) { |
92 | ans[i] = 0; |
93 | } |
94 | scanf("%d", &Q); |
95 | n = q = 0; |
96 | for (int i = 1, type, x, y, z, lx, ly, lz, rx, ry, rz; i <= Q; i++) { |
97 | scanf("%d", &type); |
98 | if (type == 1) { |
99 | scanf("%d %d %d", &x, &y, &z); |
100 | add_event(0, x, y, z); |
101 | } else { |
102 | scanf("%d %d %d %d %d %d", &lx, &ly, &lz, &rx, &ry, &rz); |
103 | lx--, ly--, lz--, q++; |
104 | add_event(q, rx, ry, rz); |
105 | add_event(-q, lx, ry, rz); |
106 | add_event(-q, rx, ly, rz); |
107 | add_event(-q, rx, ry, lz); |
108 | add_event(q, rx, ly, lz); |
109 | add_event(q, lx, ry, lz); |
110 | add_event(q, lx, ly, rz); |
111 | add_event(-q, lx, ly, lz); |
112 | } |
113 | } |
114 | for (int i = 1; i <= n; i++) { |
115 | tmp[i] = eve[i].z; |
116 | } |
117 | sort(tmp + 1, tmp + n + 1); |
118 | sz = unique(tmp + 1, tmp + n + 1) - (tmp + 1); |
119 | for (int i = 1; i <= n; i++) { |
120 | eve[i].z = lower_bound(tmp + 1, tmp + sz + 1, eve[i].z) - tmp; |
121 | } |
122 | cdq(1, n); |
123 | for (int i = 1; i <= q; i++) { |
124 | printf("%d\n", ans[i]); |
125 | } |
126 | } |
127 | return 0; |
128 | } |
整体二分
整体二分是一种分治算法，让我们直接看题吧。
题目大意
有 $n$ 个栈，一开始为空。有 $m$ 次操作，共分两种：
1 a b c表示在第 $a$ 个栈到第 $b$ 个栈中各添加一个权值为 $c$ 的元素。2 l r k表示询问第 $l$ 个栈到第 $r$ 个栈中第 $k$ 大的元素。
数据范围：$n, m \le 5 \times 10^4$。
思路分析
想要求一个集合的第 $k$ 大，考虑使用二分的方法。每次查询 $> x$ 的数的个数，设结果为 $y$。如果 $y < k$，则答案 $\le x$；否则，答案 $>x$。
但是发现 $1$ 操作不好用数据结构维护，不能在线地做二分。考虑离线，然后使用整体二分的方法。具体地，我们定义函数 solve(A[], L, R)，其中 $A$ 表示所有操作形成的序列，$L, R$ 表示 $A$ 中所有的修改涉及到的数，以及所有询问的答案都在区间 $[L, R]$ 内部，也就是分治的子问题。为了方便起见，我们令 $M$ 表示区间 $[L, R]$ 的中点，也就是 $\lfloor \frac{L + R}{2} \rfloor$。
我们考虑通过 solve 函数把原问题递归到它的子问题。也就是说，我们要判断 $A$ 中的每个询问的答案是否 $\le M$。对 $c_i > M$ 的修改和所有询问按照发生的时间依次考虑，我们要计算对于每个询问，有多少 $> M$ 的数在它的区间内部。使用支持区间加法，区间查询的线段树即可。我们将计算结果记作 $\text{res}(i)$，并新建两个序列 $A_l, A_r$，表示递归到左边的序列和递归到右边的序列。
之后，扫一遍 $A$。如果某个元素是修改，则根据它的 $c$ 将其加入 $A_l$ 或 $A_r$ 中。如果是询问，就将 $\text{res(i)}$ 和 $k_i$ 做比较。如果 $\text{res(i)} \ge k_i$，则将它放入 $A_{r}$ 中；否则将它放到 $A_l$ 中，并将 $k_i \leftarrow k_i - \text{res}(i)$，因为已经有 $\text{res}(i)$ 个数排在它前面了。最后，递归求解 solve(Al, L, M) 以及 solve(Ar, M + 1, R) 即可。不难发现最多递归的层数是 $\log c$，并且每层最多有 $m$ 个元素。再加上线段树的复杂度 $O(\log n)$，总共的复杂度是 $O(m \log n \log c)$，可以通过本题。
代码实现
1 | |
2 | |
3 | |
4 | |
5 | using namespace std; |
6 | |
7 | typedef long long ll; |
8 | const int maxn = 5e4, maxm = maxn << 2; |
9 | int n, m, q, ans[maxn + 3]; |
10 | ll tag[maxm + 3], sum[maxm + 3], res[maxn + 3]; |
11 | |
12 | struct event { |
13 | int id, a, b, c; |
14 | } e[maxn + 3], tmp[maxn + 3]; |
15 | |
16 | void push_down(int rt, int l, int r) { |
17 | tag[ls] += tag[rt], sum[ls] += tag[rt] * (mid - l + 1); |
18 | tag[rs] += tag[rt], sum[rs] += tag[rt] * (r - mid); |
19 | tag[rt] = 0; |
20 | } |
21 | |
22 | void maintain(int rt) { |
23 | sum[rt] = sum[ls] + sum[rs]; |
24 | } |
25 | |
26 | ll query(int rt, int l, int r, int lx, int rx) { |
27 | if (l >= lx && r <= rx) { |
28 | return sum[rt]; |
29 | } |
30 | push_down(rt, l, r); |
31 | ll ans = 0; |
32 | if (lx <= mid) { |
33 | ans += query(ls, l, mid, lx, rx); |
34 | } |
35 | if (rx > mid) { |
36 | ans += query(rs, mid + 1, r, lx, rx); |
37 | } return ans; |
38 | |
39 | } |
40 | |
41 | void modify(int rt, int l, int r, int lx, int rx, int x) { |
42 | if (l >= lx && r <= rx) { |
43 | tag[rt] += x, sum[rt] += (r - l + 1) * x; |
44 | return; |
45 | } |
46 | push_down(rt, l ,r); |
47 | if (lx <= mid) { |
48 | modify(ls, l, mid, lx, rx, x); |
49 | } |
50 | if (rx > mid) { |
51 | modify(rs, mid + 1, r, lx, rx, x); |
52 | } |
53 | maintain(rt); |
54 | } |
55 | |
56 | void solve(int l, int r, int L, int R) { |
57 | if (l > r) { |
58 | return; |
59 | } |
60 | if (L == R) { |
61 | for (int i = l; i <= r; i++) { |
62 | if (e[i].id) { |
63 | ans[e[i].id] = L; |
64 | } |
65 | } |
66 | return; |
67 | } |
68 | int M = (L + R) / 2; |
69 | for (int i = l; i <= r; i++) { |
70 | if (!e[i].id && e[i].c > M) { |
71 | modify(1, 1, n, e[i].a, e[i].b, 1); |
72 | } else { |
73 | res[i] = query(1, 1, n, e[i].a, e[i].b); |
74 | } |
75 | } |
76 | for (int i = l; i <= r; i++) { |
77 | if (!e[i].id && e[i].c > M) { |
78 | modify(1, 1, n, e[i].a, e[i].b, -1); |
79 | } |
80 | } |
81 | int p = l, q = r; |
82 | for (int i = l; i <= r; i++) { |
83 | if (!e[i].id) { |
84 | if (e[i].c <= M) { |
85 | tmp[p++] = e[i]; |
86 | } else { |
87 | tmp[q--] = e[i]; |
88 | } |
89 | } else { |
90 | if (res[i] < e[i].c) { |
91 | tmp[p] = e[i]; |
92 | tmp[p++].c -= res[i]; |
93 | } else { |
94 | tmp[q--] = e[i]; |
95 | } |
96 | } |
97 | } |
98 | reverse(tmp + q + 1, tmp + r + 1); |
99 | for (int i = l; i <= r; i++) { |
100 | e[i] = tmp[i]; |
101 | } |
102 | solve(l, p - 1, L, M); |
103 | solve(p, r, M + 1, R); |
104 | } |
105 | |
106 | int main() { |
107 | scanf("%d %d", &n, &m); |
108 | for (int i = 1, t; i <= m; i++) { |
109 | scanf("%d %d %d %d", &t, &e[i].a, &e[i].b, &e[i].c); |
110 | e[i].id = t == 1 ? 0 : ++q; |
111 | } |
112 | solve(1, m, 0, n); |
113 | for (int i = 1; i <= q; i++) { |
114 | printf("%d\n", ans[i]); |
115 | } |
116 | return 0; |
117 | } |