线段树分治
线段树和离线算法的结合。假如你需要维护一些信息，这些信息会在某一个时间段内出现，要求在离线的前提下回答某一个时刻的信息并，则可以考虑使用线段树分治的技巧。
回顾线段树内容，假如需要维护一个时间轴上的操作，对这个时间轴建立线段树，把在某一时间段生效的操作挂在线段树节点上，在到达当前节点时，添加该节点上保存的操作；在离开该节点时，对于图的连通性问题通常使用可撤销并查集，对于其他特殊问题，如果需要维护的数据结构空间复杂度很小，也可以直接保存操作前的状态，离开该节点时再复制回原来的状态。询问操作一般存储在线段树叶节点上。
例题
-
维护一张图，动态添加一些边，删除一些已经存在的边，查询两个点是否连通
将操作标记上生效时间，用线段树维护时间轴
维护一个可撤销并查集
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
cin >> n >> m;
std::map<pii, std::vector<int>> mm;
std::vector<std::tuple<int, int, int>> q;
for (int i = 0; i < m; i++) {
int op, x, y;
cin >> op >> x >> y;
if (y < x) {
std::swap(x, y);
}
if (op == 0 || op == 1) {
mm[{x, y}].push_back(i);
} else {
q.emplace_back(x, y, i);
}
}
std::vector<std::vector<std::tuple<int, int, bool>>> seg(m << 2);
auto modify = [&](auto &&self, int p, int l, int r, int x, int y,
std::tuple<int, int, bool> v) -> void {
if (l >= x && r <= y) {
seg[p].emplace_back(v);
return;
}
int m = (l + r) / 2;
if (x <= m) {
self(self, p << 1, l, m, x, y, v);
}
if (y >= m + 1) {
self(self, p << 1 | 1, m + 1, r, x, y, v);
}
};
DSU dsu(n + 1);
auto dfs = [&](auto &&self, int p, int l, int r) -> void {
int cnt = 0;
for (auto [x, y, isq] : seg[p]) {
if (isq) continue;
cnt += dsu.merge(x, y);
}
if (l == r) {
for (auto [x, y, isq] : seg[p]) {
if (!isq) continue;
if (dsu.same(x, y)) {
cout << "Y\n";
} else {
cout << "N\n";
}
}
while (cnt--) {
dsu.revert();
}
return;
}
int m = (l + r) / 2;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
while (cnt--) {
dsu.revert();
}
};
for (auto &[xy, vec] : mm) {
auto [x, y] = xy;
if (vec.size() & 1) {
vec.push_back(m);
}
for (int i = 0; i < vec.size(); i += 2) {
modify(modify, 1, 0, m - 1, vec[i], vec[i + 1], {x, y, false});
}
}
for (auto [x, y, t] : q) {
modify(modify, 1, 0, m - 1, t, t, {x, y, true});
}
dfs(dfs, 1, 0, m - 1);
return 0;
} -
维护一张图是否是二分图
维护一个可撤销并查集，用扩展域并查集来判断是否是二分图
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
std::vector<std::vector<pii>> seg((k + 1) << 2);
auto modify = [&](auto && self, int p, int l, int r, int x, int y, pii v) -> void {
if (l >= x && r <= y) {
seg[p].emplace_back(v);
return;
}
int m = (l + r) / 2;
if (x <= m) {
self(self, p << 1, l, m, x, y, v);
}
if (y >= m + 1) {
self(self, p << 1 | 1, m + 1, r, x, y, v);
}
};
for (int i = 0; i < m; i++) {
int x, y, l, r;
cin >> x >> y >> l >> r;
l++;
x--;
y--;
modify(modify, 1, 0, k, l, r, {x, y});
}
DSU dsu(n * 2);
auto dfs = [&](auto && self, int p, int l, int r) -> void {
int cnt = 0;
bool check = true;
for (auto [x, y] : seg[p]) {
if (dsu.same(x, y)) {
check = false;
break;
} else {
cnt += dsu.merge(x, y + n);
cnt += dsu.merge(x + n, y);
}
}
if (l == r) {
if (l > 0) {
if (check) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
while (cnt--) {
dsu.revert();
}
return;
}
if (!check) {
for (int i = l; i <= r; i++) {
cout << "No\n";
}
while (cnt--) {
dsu.revert();
}
return;
}
int m = (l + r) / 2;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
while (cnt--) {
dsu.revert();
}
};
dfs(dfs, 1, 0, k);
return 0;
} -
找出一张图的最小 mex 树
按照边权值轴建立线段树，如果一条边的权值为 w，那么就设置它的生效时间为 $[0,w-1],[w+1,w_{max}]$，依次检查每个 $w$ 时刻能否让图连通
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87int main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
int n, m;
// cin >> n >> m;
read(n);
read(m);
int W = 100'000 + 1;
std::vector<std::vector<pii>> seg((W + 1) << 2);
auto modify = [&](auto &&self, int p, int l, int r, int x, int y,
pii v) -> void {
if (l >= x && r <= y) {
seg[p].emplace_back(v);
return;
}
int m = (l + r) / 2;
if (x <= m) {
self(self, p << 1, l, m, x, y, v);
}
if (y >= m + 1) {
self(self, p << 1 | 1, m + 1, r, x, y, v);
}
};
for (int i = 0; i < m; i++) {
int u, v, w;
read(u);
read(v);
read(w);
if (u == v) continue;
u--;
v--;
if (w - 1 >= 0) {
modify(modify, 1, 0, W, 0, w - 1, {u, v});
}
modify(modify, 1, 0, W, w + 1, W, {u, v});
}
DSU dsu(n);
int cnt = n;
bool flag = false;
auto dfs = [&](auto self, int p, int l, int r) -> void {
if (flag) return;
int t = 0;
for (auto [x, y] : seg[p]) {
if (dsu.same(x, y)) continue;
dsu.merge(x, y);
t++;
cnt--;
}
if (l == r) {
if (cnt == 1) {
print(l, '\n');
flag = true;
return;
}
cnt += t;
while (t--) {
dsu.revert();
}
return;
}
int m = (l + r) / 2;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
cnt += t;
while (t--) {
dsu.revert();
}
};
dfs(dfs, 1, 0, W);
return 0;
} -
给定一棵树，树边设置权值，$f(u,v)$ 为 $u,v$ 两点间简单路径上边权只出现一次的边权个数，同样按照边权值建立线段树，统计每条边的贡献。如果当前来到线段树叶节点 $w$，检查 $w$ 权值的所有边，由于原图是一棵树，能保证枚举当前边时，边左右两个端点的连通块一定不同，且只有当前边能让它们连通，$siz[u]\times siz[v]$ 即为当前边的贡献。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
cin >> n;
std::vector<std::vector<pii>> seg((n + 1) << 2);
auto modify = [&](auto && self, int p, int l, int r, int x, int y, pii v) -> void {
if (l >= x && r <= y) {
seg[p].emplace_back(v);
return;
}
int m = (l + r) / 2;
if (x <= m) {
self(self, p << 1, l, m, x, y, v);
}
if (y >= m + 1) {
self(self, p << 1 | 1, m + 1, r, x, y, v);
}
};
std::vector<std::vector<pii>> e(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v, x;
cin >> u >> v >> x;
u--;
v--;
e[x].emplace_back(u, v);
if (x > 1) {
modify(modify, 1, 1, n, 1, x - 1, {u, v});
}
if (x < n) {
modify(modify, 1, 1, n, x + 1, n, {u, v});
}
}
DSU dsu(n);
i64 ans = 0;
auto dfs = [&](auto && self, int p, int l, int r) -> void {
int t = 0;
for (auto [x, y] : seg[p]) {
t += dsu.merge(x, y);
}
if (l == r) {
for (auto [x, y] : e[l]) {
ans += 1LL * dsu.size(x) * dsu.size(y);
}
while (t--) {
dsu.revert();
}
return;
}
int m = (l + r) / 2;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
while (t--) {
dsu.revert();
}
};
dfs(dfs, 1, 1, n);
cout << ans << "\n";
return 0;
} -
思路同上一题
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
cin >> n >> m;
std::map<pii, std::vector<int>> mm;
std::vector<bool> haveq(m);
for (int i = 0; i < m; i++) {
char op;
int u, v;
cin >> op >> u >> v;
u--;
v--;
if (u > v) {
std::swap(u, v);
}
mm[{u, v}].push_back(i);
if (op == 'Q') {
haveq[i] = true;
}
}
std::vector<std::vector<std::tuple<int, int, bool>>> seg(m << 2);
auto modify = [&](auto && self, int p, int l, int r, int x, int y, const std::tuple<int, int, bool> &v) -> void {
if (l >= x && r <= y) {
seg[p].emplace_back(v);
return;
}
int m = (l + r) / 2;
if (x <= m) {
self(self, p << 1, l, m, x, y, v);
}
if (y >= m + 1) {
self(self, p << 1 | 1, m + 1, r, x, y, v);
}
};
for (auto &[edge, vec] : mm) {
if (vec.size() == 1) {
modify(modify, 1, 1, m, vec.front(), m, {edge.fi, edge.se, false});
continue;
}
modify(modify, 1, 1, m, vec[0], vec[1] - 1, {edge.fi, edge.se, false});
for (int i = 1; i < vec.size() - 1; i++) {
if (vec[i] + 1 <= vec[i + 1] - 1) {
modify(modify, 1, 1, m, vec[i] + 1, vec[i + 1] - 1, {edge.fi, edge.se, false});
}
}
if (vec.back() < m) {
modify(modify, 1, 1, m, vec.back() + 1, m, {edge.fi, edge.se, false});
}
for (int i = 1; i < vec.size(); i++) {
modify(modify, 1, 1, m, vec[i], vec[i], {edge.fi, edge.se, true});
}
}
DSU dsu(n);
auto dfs = [&](auto && self, int p, int l, int r) -> void {
int t = 0;
for (auto &[x, y, isq] : seg[p]) {
if (isq) continue;
t += dsu.merge(x, y);
}
if (l == r) {
for (auto &[x, y, isq] : seg[p]) {
if (!isq) continue;
cout << 1LL * dsu.size(x) * dsu.size(y) << "\n";
break;
}
while (t--) {
dsu.revert();
}
return;
}
int m = (l + r) / 2;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
while (t--) {
dsu.revert();
}
};
dfs(dfs, 1, 1, m);
return 0;
} -
模板题
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
cin >> n >> m;
std::vector<pii> e;
e.reserve(m);
std::vector<std::vector<int>> opt(m);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
e.emplace_back(u, v);
}
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int t;
cin >> t;
while (t--) {
int x;
cin >> x;
x--;
opt[x].push_back(i + 1);
}
}
std::vector<std::vector<int>> seg((k + 1) << 2);
auto modify = [&](auto && self, int p, int l, int r, int x, int y, int v) -> void {
if (l >= x && r <= y) {
seg[p].emplace_back(v);
return;
}
int m = (l + r) / 2;
if (x <= m) {
self(self, p << 1, l, m, x, y, v);
}
if (y >= m + 1) {
self(self, p << 1 | 1, m + 1, r, x, y, v);
}
};
for (int i = 0; i < m; i++) {
int siz = opt[i].size();
if (siz == 0) {
modify(modify, 1, 0, k, 0, k, i);
} else {
modify(modify, 1, 0, k, 0, opt[i][0] - 1, i);
for (int j = 0; j < siz - 1; j++) {
if (opt[i][j] + 1 <= opt[i][j + 1] - 1) {
modify(modify, 1, 0, k, opt[i][j] + 1, opt[i][j + 1] - 1, i);
}
}
if (opt[i][siz - 1] + 1 <= k) {
modify(modify, 1, 0, k, opt[i][siz - 1] + 1, k, i);
}
}
}
DSU dsu(n);
auto dfs = [&](auto && self, int p, int l, int r) -> void {
int t = 0;
for (auto i : seg[p]) {
auto [x, y] = e[i];
t += dsu.merge(x, y);
}
if (l == r) {
if (l > 0) {
if (dsu.size(0) == n) {
cout << "Connected\n";
} else {
cout << "Disconnected\n";
}
}
while (t--) {
dsu.revert();
}
return;
}
int m = (l + r) / 2;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
while (t--) {
dsu.revert();
}
};
dfs(dfs, 1, 0, k);
return 0;
} -
初始给定一张图，边没有颜色，每次操作将边染上一种指定颜色，操作后，判断所有颜色中仅由该种颜色形成的图是否是二分图，如果是，保留操作，否则撤销这次操作。
由于不合法则撤销，所以能保证每种颜色的边组成的图始终是二分图。如果将一条边由原来的 $old$ 色变为 $new$ 色，可以确保如果操作成功后，$old$ 色减少一条边，仍是二分图，所以我们只需要判断 $new$ 色的边加入当前一条新边后是否是二分图即可。
该题目难点在于当前操作有可能被撤销，从而维持当前边之前的颜色。我们先按照经典的方式将所有操作加入时间轴线段树中，同时维护一个 $last$ 数组，表示 $last_i$ 为第 $i$ 条边上次的颜色，每次对边的染色操作从 $last_i$ 取出颜色，如果发现当前操作染色成功，则 $last_i=new$，否则不变。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, k, q;
cin >> n >> m >> k >> q;
std::vector<pii> e;
e.reserve(m);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
if (u > v) {
std::swap(u, v);
}
e.emplace_back(u, v);
}
std::vector<int> last(m, -1);
std::vector<std::vector<int>> seg(q << 2);
std::vector<pii> query(q);
std::vector<int> opt(m, -1);
auto modify = [&](auto && self, int p, int l, int r, int x, int y, int v) -> void {
if (l >= x && r <= y) {
seg[p].push_back(v);
return;
}
int m = (l + r) / 2;
if (x <= m) {
self(self, p << 1, l, m, x, y, v);
}
if (y >= m + 1) {
self(self, p << 1 | 1, m + 1, r, x, y, v);
}
};
for (int i = 0; i < q; i++) {
int x, color;
cin >> x >> color;
x--;
color--;
query[i] = {x, color};
if (~opt[x]) {
modify(modify, 1, 0, q - 1, opt[x] + 1, i, x);
}
opt[x] = i;
}
for (int i = 0; i < m; i++) {
if (opt[i] < q - 1 && opt[i] != -1) {
modify(modify, 1, 0, q - 1, opt[i] + 1, q - 1, i);
}
}
std::vector<DSU> dsu(k, DSU(n * 2));
auto dfs = [&](auto && self, int p, int l, int r) -> void {
std::vector<int> change;
change.reserve(32);
for (int edge : seg[p]) {
auto [x, y] = e[edge];
int color = last[edge];
if (color == -1) continue;
int t = 0;
t += dsu[color].merge(x, y + n);
t += dsu[color].merge(x + n, y);
while (t--) {
change.push_back(color);
}
}
if (l == r) {
auto [x, color] = query[l];
auto [u, v] = e[x];
int nw = color;
auto &d = dsu[nw];
if (d.same(u, v)) {
cout << "NO\n";
} else {
cout << "YES\n";
last[x] = nw;
}
for (int c : change) {
dsu[c].revert();
}
return;
}
int m = (l + r) / 2;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
for (int c : change) {
dsu[c].revert();
}
};
dfs(dfs, 1, 0, q - 1);
return 0;
} -
给定一个内向基环森林，每次询问指定 k 种颜色，可以选择将每个点及其能到达的所有点染色，同时会修改一个点的出边，问对于每次询问，这个图最终会有多少种颜色不同的情况，答案对 3 取模。
由于每次修改一条出边，形成的图仍旧是内向基环森林，分析不难得到假如整个图的 SCC 数量为 $c$，则对应答案为 $k^c \mod 3$，下面分析一下这个答案：
- $k \equiv 0(\mod 3)\rightarrow k^c \equiv 0(\mod 3)$
- $k\equiv 1 (\mod 3)\rightarrow k^c (\mod 3)$
- $k\equiv 2(\mod 3)\rightarrow k^c\equiv 1(\mod 3)\text{ if k is even} , k^c\equiv 2(\mod 3)\text{ if k is odd}$
统计强连通分量的数量很困难，因为通过并查集很难得出环的大小，但是可以很容易地得到环大小的奇偶性，因此只需要维护一个 $dis$ 带权并查集，就可以在合并时得到环的奇偶性
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
cin >> n >> q;
std::vector<std::vector<pii>> opt(n);
std::vector<int> query(q + 1);
for (int i = 0; i < n; i++) {
int g;
cin >> g;
g--;
opt[i].push_back({g, 0});
}
for (int i = 1; i <= q; i++) {
int x, y, k;
cin >> x >> y >> k;
query[i] = k;
x--;
y--;
opt[x].push_back({y, i});
}
std::vector<std::vector<pii>> seg((q + 1) << 2);
auto modify = [&](auto &&self, int p, int l, int r, int x, int y,
const pii &v) -> void {
if (l >= x && r <= y) {
seg[p].push_back(v);
return;
}
int m = (l + r) / 2;
if (x <= m) {
self(self, p << 1, l, m, x, y, v);
}
if (y >= m + 1) {
self(self, p << 1 | 1, m + 1, r, x, y, v);
}
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < opt[i].size() - 1; j++) {
modify(modify, 1, 0, q, opt[i][j].se, opt[i][j + 1].se - 1,
{i, opt[i][j].fi});
}
if (opt[i].size()) {
modify(modify, 1, 0, q, opt[i].back().se, q, {i, opt[i].back().fi});
}
}
bool odd = n & 1;
DSU dsu(n);
auto dfs = [&](auto &&self, int p, int l, int r) -> void {
int t = 0;
bool todd = odd;
for (auto [x, y] : seg[p]) {
if (dsu.same(x, y)) {
int dx = dsu.getd(x);
int dy = dsu.getd(y);
if ((dx + dy) & 1) {
odd ^= 1;
}
} else {
dsu.merge(x, y);
t++;
}
}
if (l == r) {
if (l > 0) {
int k = query[l] % 3;
if (k == 0 || k == 1) {
cout << k << "\n";
} else {
cout << (odd ? 2 : 1) << "\n";
}
}
while (t--) {
dsu.revert();
}
odd = todd;
return;
}
int m = (l + r) / 2;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
while (t--) {
dsu.revert();
}
odd = todd;
};
dfs(dfs, 1, 0, q);
return 0;
}
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Related Articles
2025-08-17
SOS-DP 详解
简介SOS-DP，英文名 Sum over Subsets(SOS) dynamic programming，即子集和DP，用来求某一集合的所有子集对应状态之和。 给定一个含 $2^N$ 个元素的集合 $A$，下标用 $i$ 来表示，求一个 $F_{state}$，对应为：$$F_{state}=\sum_{i\subseteq state / i \text{&} state = state}A[i]$$ 解法： Bruteforce1234567for (int mask = 0; mask < (1 << N); mask++) { for (int i = 0; i < (1 << N); i++) { if ((mask & i) == i) { F[mask] += A[i]; } }} 对于每个 $mask$，暴力枚举哪些状态为它的子集，时间复杂度 $O(4^N)$ Suboptimal...
2025-08-19
可持久化并查集和可撤销并查集
可持久化并查集可以查询任意版本的并查集，本质就是可持久化数组，将 $f$ 数组与 $siz$ 可持久化 为了减少每次合并操作的修改元素数量，只做按秩合并，不做路径压缩。假设要合并 $a$ 所在元素集合和 $b$ 所在元素集合，集合代表节点和集合大小分别为 $f_a,siz_a,f_b,siz_b(siz_a>siz_b)$，这样每次合并的操作就只有 $f[f_b]=f_a $ $siz[f_a]=siz_a+siz_b$ 只需进行两次操作，大大减小了操作量，并且由于启发式合并，每次查询操作也只会跳转 $O(\log n)$ 次。 可撤销并查集可以按照FIFO回滚所做操作，用一个栈来存储当前版本修改了哪些信息，以便回退到它上一个版本。 由于只维护了两个集合代表节点在合并时的相关信息，同样不能做路径压缩 模板 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758struct DSU...
2025-08-21
线段树分治（2）
上一章中介绍到使用可撤销并查集结合线段树分治可以维护图的连通性信息。由于在同一时间线段树的深度为 $O(\log q)$ ，因此可以利用直接复制的操作，如果数据结构大小为 $n$，则总的时间复杂度为 $O(nq\log q)$ CF601E 维护背包问题的 dp 数组： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, k; cin >> n >> k; std::vector<Z> fac(k); ...
Comments
