【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想

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

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

Description

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

Notes

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

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

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

// 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;
	}
};

对于$B$，在合并时同时记录$B$ 中元素的答案。

对于$A$，不遍历其中元素的前提下如何记录答案？

• 用 懒标记 LazyTag 记录$A$ 这个整体需要加上多少答案；
• 在集合$A$ 销毁（即合并到其它集合上）时，再将懒标记 LazyTag 分配给每个元素；
• 将另一个集合$B$ 合并到已有懒标记 LazyTag 的集合$A$ 时，需要给$B$ 的每个元素减去$A$ 已有的标记。

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

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];
}

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

Code

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

给定$N$ 点有向图，点有颜色，颜色编号不超过$n$。输入$m$ 对无序颜色对$x,y$（可能出现$x=y$），如果点$u, v\ (u<v)$ 的颜色恰好分别为$x,y$ 或$y,x$，则连边$u\to v$。求$1$ 到$N$ 的路径数量，结果对$10^9+7$ 取模。$n,m,N \leqslant 2\cdot 10^{5}$。

Notes

设$dp_{x}$ 表示$1$ 到$x$ 的路径数量，有朴素递推式

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

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

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

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];
}

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

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

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

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 = \dfrac{2m}{B}$ 个度数超过$B$ 的点，询问小点的复杂度是$\operatorname{O}(B)$，询问大点的复杂度是$\operatorname{O}(1)$，此外每次询问更新大点还需时间$\operatorname{O}(k)=\operatorname{O}\Big(\dfrac{2m}{B}\Big)$，总时间复杂度是$\operatorname{O}\bigg[m + q \cdot\max\Big(B, \dfrac{2m}{B}\Big)\bigg]$。取$B=\sqrt{2m}$ 最优，故也称 根号分治，适合$10^{4}\sim 2\cdot 10^{5}$ 的数据范围。最终时间复杂度$\operatorname{O}(q\sqrt{ m})$。

Code

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

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

Notes

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

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

Code

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;
}