想必读者第一次听说懒标记 (LazyTag) 是在线段树区间修改中,其实懒标记思想在图论及更多方面中也有应用。其核心思想在于「延迟计算」,即通过标记的方式记录对某个有相同性质的对象(如线段树的区间、图中的连通块等)的 整体操作,而不是立即操作每个元素。

一、并查集维护连通性——The 2025 ICPC Latin America Championship D. Dangerous City

Description

给定无向图,有点权。路径权值定义为路径上(含端点)所有点权最大值,定义 f(u,v)f(u, v) 为所有 uu 到 vv 路径中值最小的一条。对每个uu 求 su=v=1nf(u,v)s_u = \displaystyle \sum_{v=1}^n f(u, v)n,m3105n,m \leqslant 3\cdot 10^{5}

Notes

将点权转化为边权,设uvu-v 的边权w=max{wu,wv}w=\max\lbrace w_{u},w_{v} \rbrace,则路径权值就是路径上边权最大值。

Kruskal 的想法,按边权从小到大遍历这些边。两点u,vu,v 第一次连通时,当前遍历的边权ww 就是 f(u,v)f(u, v)。遍历每条边后,将这条边两个端点所在的连通块合并,用并查集维护图连通性(并查集维护无向图连通性其实是并查集的本质)。设将连通块 A,BA, B 合并,则这条边对 AA 中所有点的贡献为 w×Bw \times |B|,对 BB 中所有点的贡献为 w×Aw \times |A|

由于需要记录连通块的具体元素,我们选择 并查集启发式合并不妨设AB|A| \geqslant |B|,则BB 可以遍历,AA 不能遍历。 并查集合并时将BB 中所有元素加入AA,可以证明复杂度是O(nlogn)\operatorname{O}(n\log n)。并查集启发式合并 code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// DSU
vector<int> dsuRoot(n);
vector<vector<int>> dsuElem(n);
for (int i = 0; i < n; i++) {
dsuRoot[i] = i;
dsuElem[i].push_back(i);
}
auto uno = [&](int u, int v) {
u = dsuRoot[u];
v = dsuRoot[v]; // 并查集找根
if (u == v) {
continue; // 如果已经在同一个集合里,就不需要合并
}
if (dsuElem[u].size() < dsuElem[v].size()) {
swap(u, v); // 让小集合合并到大集合里
}
for (auto x : dsuElem[v]) {
dsuElem[u].push_back(x); // 合并
dsuRoot[x] = u;
}
};

对于BB,在合并时同时记录BB 中元素的答案。

对于AA,不遍历其中元素的前提下如何记录答案?

  • 懒标记 LazyTag 记录AA 这个整体需要加上多少答案;
  • 在集合AA 销毁(即合并到其它集合上)时,再将懒标记 LazyTag 分配给每个元素;
  • 将另一个集合BB 合并到已有懒标记 LazyTag 的集合AA 时,需要给BB 的每个元素减去AA 已有的标记。

上面的过程可以与线段树区间修改类比。对于一个较大的待修改区间,我们无需一一遍历,而是打个懒标记 LazyTag,表示整体操作。当需要访问这区间的某个子区间时,再将懒标记 LazyTag 下传给左右子树,同时删除原有标记。

1
2
3
4
5
lazy[u] += 1ll * dsuElem[v].size() * w;
lazy[v] += 1ll * dsuElem[u].size() * w;
for (auto x : dsuElem[v]) {
val[x] += lazy[v] - lazy[u];
}

总时间复杂度O(mlogn)\operatorname{O}(m\log n)

Code

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
int n, m;
cin >> n >> m;
vector<ll> val(n);
for (auto& x : val) {
cin >> x;
}
vector<array<int, 3>> edge(m);
for (auto& [w, u, v] : edge) {
cin >> u >> v;
u--, v--;
w = max(val[u], val[v]); // 将点权转化为边权
}
sort(edge.begin(), edge.end()); // 按边权从小到大遍历
// DSU
vector<int> dsuRoot(n);
vector<vector<int>> dsuElem(n);
for (int i = 0; i < n; i++) {
dsuRoot[i] = i;
dsuElem[i].push_back(i);
}
// main
vector<ll> lazy(n);
for (auto [w, u, v] : edge) { // 按边权从小到大遍历
u = dsuRoot[u];
v = dsuRoot[v]; // 并查集找根
if (u == v) continue; // 如果已经在同一个集合里,就不需要合并
if (dsuElem[u].size() < dsuElem[v].size()) swap(u, v); // 让小集合合并到大集合里
lazy[u] += 1ll * dsuElem[v].size() * w;
lazy[v] += 1ll * dsuElem[u].size() * w;
for (auto x : dsuElem[v]) {
val[x] += lazy[v] - lazy[u];
dsuElem[u].push_back(x); // 合并
dsuRoot[x] = u;
}
}
for (int x = 0; x < n; x++) {
val[x] += lazy[dsuRoot[x]]; // 将懒标记加到每个点上
cout << val[x] << " ";
}
cout << endl;

二、根号分治——2025 春 杭电多校 04 1010 图之图

在学习本题前请先熟悉 无向图转化为有向图思想洛谷 P1989 无向图三元环计数)与 图论根号分治思想(经典中的经典之 Hammer to Fall,用 multiset,和官方题解做法不太一样)。

Description

给定NN 点有向图,点有颜色,颜色编号不超过nn。输入mm 对无序颜色对x,yx,y(可能出现x=yx=y),如果点u,v (u<v)u, v\ (u<v) 的颜色恰好分别为x,yx,yy,xy,x,则连边uvu\to v。求11NN 的路径数量,结果对109+710^9+7 取模。n,m,N2105n,m,N \leqslant 2\cdot 10^{5}

Notes

dpxdp_{x} 表示11xx 的路径数量,有朴素递推式

dpx={1,x=1,yxdpy,otherwise.dp_{x} = \begin{cases} 1, & x=1, \\ \sum_{y\to x}dp_{y}, &\text{otherwise}. \end{cases}

不能暴力建图,边数可能达到N2N^{2},复杂度为O(N3)\operatorname{O}(N^{3})。于是 按颜色建图,这样点数边数分别为n,mn,m

val(u)\operatorname{val}(u) 表示颜色为uu 的所有点的 dp 值之和,那么先更新dpx=vuval(v)dp_{x}=\sum_{v\to u}\operatorname{val}(v),再更新val(u)dpx\operatorname{val}(u)\leftarrow dp_{x},其中uu 表示xx 的颜色。

1
2
3
4
5
6
7
8
9
10
vector<Z> val(n), dp(N);
for (int x = 0; x < N; x++) {
int u = color[x];
if (x == 0) {
dp[x] = 1;
} else for (auto v : E[u]) {
dp[x] += val[v];
}
val[u] += dp[x];
}

现在的时间复杂度为O(Nm)\operatorname{O}(Nm),仍然不能通过。问题出在度数较大的点(下称大点)需要遍历很多边,复杂度较高。

小点行动敏捷,而大点体型庞大步履维艰。于是大点压榨奴役小点,让小点自己暴力更新后,再把信息送给大点,为大点的更新做好准备(真过分呢)。

按点的大小分治。对于大点,设lazy(u)\operatorname{lazy}(u) 表示uu 相邻点的 dp 值之和。如果uu 是小点,仍按上述式子朴素递推;如果uu 是大点,那么dpx=lazy(u)dp_{x}=\operatorname{lazy}(u)。转移 dp 后需更新相邻大点vv 的 lazy,令lazy(v)dpx\operatorname{lazy}(v)\leftarrow dp_{x}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<Z> val(n), lazy(n), dp(N);
for (int x = 0; x < N; x++) {
int u = color[x];
if (x == 0) {
dp[x] = 1;
} else if (E[u].size() > B) { // 大点直接用lazyTag
dp[x] = lazy[u];
} else for (auto v : E[u]) { // 小点暴力更新
dp[x] += val[v];
}
val[u] += dp[x];
for (auto v : G[u]) { // 把信息送给大点
lazy[v] += dp[x];
}
}

复杂度分析:设有k=2mBk = \dfrac{2m}{B} 个度数超过BB 的点,询问小点的复杂度是O(B)\operatorname{O}(B),询问大点的复杂度是O(1)\operatorname{O}(1),此外每次询问更新大点还需时间O(k)=O(2mB)\operatorname{O}(k)=\operatorname{O}\Big(\dfrac{2m}{B}\Big),总时间复杂度是O[m+qmax(B,2mB)]\operatorname{O}\bigg[ m + q \cdot\max\Big(B, \dfrac{2m}{B}\Big)\bigg]。取B=2mB=\sqrt{ 2m } 最优,故也称 根号分治,适合104210510^{4}\sim 2\cdot 10^{5} 的数据范围。最终时间复杂度O(qm)\operatorname{O}(q\sqrt{ m })

Code

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
int N, n;
cin >> N >> n;
vector<int> color(N);
for (int i = 0; i < N; i++) {
cin >> color[i];
color[i]--;
}
vector<vector<int>> E(n);
int m;
cin >> m;
const int B = ceil(sqrt(2 * m));
while (m--) {
int u, v;
cin >> u >> v;
u--;
v--;
E[u].push_back(v);
if (u != v) { // 注意自环
E[v].push_back(u);
}
}
vector<vector<int>> G(n);
for (int u = 0; u < n; u++) {
for (auto v : E[u]) {
if (E[v].size() > B) {
G[u].push_back(v); // 所有点连大点
}
}
}
vector<Z> val(n), lazy(n), dp(N);
for (int x = 0; x < N; x++) {
int u = color[x];
if (x == 0) {
dp[x] = 1;
} else if (E[u].size() > B) { // 大点直接用lazyTag
dp[x] = lazy[u];
} else for (auto v : E[u]) { // 小点暴力更新
dp[x] += val[v];
}
val[u] += dp[x];
for (auto v : G[u]) { // 把信息送给大点
lazy[v] += dp[x];
}
}
cout << dp.back() << endl;

三、二叉树分治——杭电多校 1004 - 传送

在学习本题前请先熟悉 可撤销并查集(用栈实现的,有别于可持久化并查集)与 二叉树分治(也称线段树分治),并完成 洛谷 P5787

Description

给定一个nn 节点的图,在nn 时间内有mm 条边会出现后消失,求出每个节点与节点 1 连通的时间编号之和,输出每个节点答案的异或和。n,m6105n,m \leqslant 6\cdot 10^{5}

Notes

这种边会出现后消失的动态连通性问题,对时间建立二叉树,分治解决。

天才的 LazyTag:递归到叶,也即到达某个确定的时刻时,对当前 1 所在的连通块的根节点打上一个 LazyTag,表示整个连通块需要加上这个值。设uuvv 的祖先,如果断开u,vu,v,需要将vv 加上uu 的 LazyTag;如果连接u,vu,v,需要将vv 减去uu 的 LazyTag。

Code

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
struct DSU {
vector<int> p, siz;
vector<ll> lazy;
vector<pair<int, int>> op;
vector<pair<int*, int>> his;
DSU(int n) : p(n), siz(n, 1), lazy(n) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (x != p[x]) x = p[x]; return x; }
bool same(int x, int y) { return find(x) == find(y); }
bool uno(int x, int y) {
x = find(x), y = find(y);
if (same(x, y)) return false;
if (siz[x] < siz[y]) swap(x, y);
his.emplace_back(&siz[x], siz[x]);
siz[x] += siz[y];
his.emplace_back(&p[y], p[y]);
p[y] = x;
// 魔改DSU,记录每个点的 lazy 值
op.emplace_back(x, y);
lazy[op.back().second] -= lazy[op.back().first];
return true;
}
int now() { return his.size(); } // 返回当前时间 h
void undo(int h) { // undo 到 h
while (now() > h) {
*his.back().first = his.back().second;
his.pop_back();
*his.back().first = his.back().second;
his.pop_back();
// 魔改DSU,记录每个点的 lazy 值
lazy[op.back().second] += lazy[op.back().first];
op.pop_back();
}
}
};

int main() {
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((L+R)>>1)

int n, m;
cin >> n >> m;

vector<vector<pair<int, int>>> E(n << 2);
while (m--) {
int u, v, l, r;
cin >> u >> v >> l >> r;
u--, v--;
l--;
if (u > v) swap(u, v);
auto add = [&](this auto&& add, int p, int L, int R) -> void {
if (l <= L && R <= r) {
E[p].push_back({ u, v });
} else if (l < R && L < r) {
add(ls, L, mid), add(rs, mid, R);
}
};
add(1, 0, n);
}

DSU dsu(n);
auto solve = [&](this auto&& solve, int p, int L, int R) -> void {
int h = dsu.now();
for (auto [u, v] : E[p]) {
dsu.uno(u, v);
}
if (R - L == 1) {
dsu.lazy[dsu.find(0)] += L + 1;
} else {
solve(ls, L, mid), solve(rs, mid, R);
}
return dsu.undo(h);
};
solve(1, 0, n);

ll res = 0;
for (int i = 0; i < n; i++) {
res ^= dsu.lazy[i];
}
cout << res << endl;

return 0;
}