P15417 「yrOI R1」彼时蓝星这题如果只看题面会以为出题人是来收作文素材的读完才会发现它其实是一道非常规整的动态图连通性问题。题目把 n 颗蓝星之间的相遇与别离做成了 m 条只存活一段时间的边再丢给你 q 个时刻问某两个星球在“彼时”是否还通过一条发光路径连在一起。如果每次询问都现场跑一遍并查集或 BFS数据稍微大一点就直接爆炸而线下的 LCT 写法成本和调试成本又不低。用线段树分治配合可撤销并查集可以把所有操作彻底离线把“删边”变成“撤回刚加的边”思路清晰、代码量也能接受非常适合用来加深对离线数据结构、分治思想以及回滚并查集的理解。这篇题解适合正在备战省选及以下难度比赛、想补动态图连通性套路的同学参考。1. 拿到题先把梦幻剧情翻译成现实模型1.1 题面里到底藏了一个什么问题原题的叙事可以简单概括成古时候蓝星的上空有很多星星每颗星星只在某一段时间里发着光当两颗星星同时发光时它们之间存在一条“星轨连接”。询问则是给定一个时刻问两颗指定的星球之间是否被星轨直接或间接连通。把蓝星当成图的节点把星轨连接当成图的边把发光时间看成每条边存活的时间区间题目立刻变成一个经典模型动态图连通性。具体地说有一张 n 个点的图图上的 m 条边各有自己的存在区间 [L_i, R_i]另有 q 次询问每次给出时间点 t 和两个点 u, v要回答在 t 时刻 u 和 v 是否连通。这个抽象过程非常关键。题目叙事越浪漫背后的数据结构越朴素。不要被“蓝星”“彼时”这些词带走竞赛题考察的是你在模型层能不能把故事剥掉。哪怕它改叫“海边灯塔”“星空观测站”或者“时间裂隙”本质都是一样的带时间戳的图上连通性查询。1.2 举个小样例为了后面讲算法方便我这里给出一组非常小的自造样例读者可以手算一遍3 3 3 1 2 1 3 2 3 2 4 1 3 1 2 1 1 3 3 1 3 4 1 3含义是三个点、三条边、三个询问。边 1 连接 1 和 2只在时间 1 到 3 存在边 2 连接 2 和 3只在时间 2 到 4 存在边 3 连接 1 和 3只在时间 1 到 2 存在。时刻 1边 1 和边 3 都存在1 和 3 直接相连答案是 Yes。时刻 3边 1 存在边 2 存在路径 1—2—3 连通答案也是 Yes。时刻 4边 1 已经没了边 3 也早没了只剩下边 2 连接 2—31 和 3 不连通答案是 No。这就是最简单的“某时刻图上是否连通”的判定。可以看到如果我们只维护一个静态并查集那么在图上加点、删点、查询三者混在一起处理起来并不容易。1.3 在线做法的麻烦最朴素的想法是对每个询问把 t 时刻还存在的边全部拉出来重新跑一遍并查集。但 m 和 q 到 1e5 级别时单次检查就要扫全图复杂度 O(qm)完全不可接受。稍微专业一点的想法是用 LCTLink-Cut Tree在线维护动态森林删边加边查询都是 O(log n)。这确实能解决题目但 LCT 的 splay、access、makeroot 一套下来篇幅不小比赛高压环境下写错一个 rotate 的方向就得调半天。而绝大多数时候我们遇到的信息学竞赛题并不强制在线完全可以离线处理。离线之后动态图连通性问题就有了更亲民的解法线段树分治 可撤销并查集。2. 离线解决动态连通性的核心算法2.1 线段树分治的思路线段树分治的核心思想是把“时间”看成下标建一棵线段树。每条边不是活在整条时间轴上而是活在某个区间 [L, R] 上那就把这个区间塞进线段树中让这条边恰好覆盖线段树上的一些节点。具体规则是把边插入线段树时用类似区间加的方式递归当某个线段树节点代表的区间完全被 [L, R] 包含时就把这条边存进这个节点的 vector 里不再继续下传。这样一来一条边最多被拆成 O(log T) 份T 是时间轴长度。之后做一次深度优先遍历进入线段树的一个节点时先把这个节点上存的边全部加入并查集如果到了叶子节点此时并查集里恰好包含了这个叶子时刻所有仍然存活的边就在这里处理该时刻的所有询问然后递归进入左右子树从节点回溯时要把该节点加入的边全部“撤销”。这里有一个解释给队友听非常有效的比喻想象你在玩一个单存档游戏进入一个分岔路口之前先存个档走完左分支读档回到路口再走右分支。两支探索之间不会互相污染。线段树分治正是这样DFS 时每次进入子树前保存现场离开子树后恢复现场兄弟分支看到的是完全一样的世界。2.2 可撤销并查集为什么能撤普通并查集之所以支持不了删边是因为它在合并时把很多节点的 father 直接指到了根路径压缩让并查集树变得非常扁平但也让你没法知道“哪条边”导致了哪些 father 变化没法回退到指定时间点。可撤销并查集放弃路径压缩改用按秩合并通常按子树大小合并并且每次真正修改 father 或 size 时都留下“操作日志”。具体做法是把合并过程写到栈上。比如要把 ra 的父亲指向 rb同时更新 rb 的 size那么就在入栈前记录下 fa[ra] 原来的值和 sz[rb] 原来的值。需要回退时从栈顶弹出最近一次操作把这两个变量还原。这样就能实现完美的“撤销上一步”。路径压缩不能用的原因也很好理解压缩会把路径上一大堆节点全部直接挂到根这些节点可能来自之前很多不同的合并步骤。回滚时你根本不知道应该恢复哪几个节点。按秩合并则保证每次合并时树高是 O(log n)查询 find 的复杂度是 O(log n)所以可撤销并查集的单次加边、单次查询复杂度都能接受。2.3 复杂度到底是多少设 n,m,q 在同一量级T 是离散化后的时间点数最多是询问时刻的不同值个数。每条边的存在区间插入线段树会被拆到 O(log T) 个节点上所以所有节点存储的边总数是 O(m log T)。DFS 访问每个线段树节点一次每遇到一条边就做一次 merge总 merge 次数等于存储的边数单次 merge 因为按秩合并是 O(log n)所以并查集部分的总复杂度是 O(m log T log n)。每个询问只会在对应叶子节点被回答一次单次 connected 查询 O(log n)因此询问部分为 O(q log n)。总时间复杂度为 O((m log T q) log n)空间复杂度为 O(m log T n)。看起来有两个 log但对于 1e5 级别的数据log 大约就是 16 到 17实际跑起来非常稳。3. 完整实现与代码细节3.1 数据结构怎么搭整体程序需要四个数据容器seg[o]线段树节点 o 上存储的边集合边用{u, v}表示。asks[leaf]挂在叶子节点上的询问集合询问记录{u, v, id}。RollbackDSU支持合并、查询、回滚的并查集结构。一个答案数组ans[]在 DFS 到叶子节点时随手填。线段树数组可以用vectorEdge seg[MAXN 2]MAXN 取询问时间点数量或 m 的总量级 5。询问为什么挂在叶子上因为 DFS 到叶子节点时路径上所有祖先节点加入的边都会被并查集维护着此时并查集里恰好是这一时刻所有存活的边直接查询就是答案。挂在节点内部反而复杂完全没有必要。3.2 边的区间如何映射到时间线段树输入里的边区间是 [L, R]时间是整数但询问只发生在某些具体时刻。更聪明的做法不是把整段时间轴都建出来而是只对询问中出现过的时刻做离散化。我的做法是把每个询问的时间 t 收集起来排序去重得到times数组。设times长度为 T。对于每条边 [l, r]用lower_bound(times.begin(), times.end(), l)得到左端点对应的离散化下标 L。它的含义是从第一个不小 l 的询问时刻开始这条边就存在了。用upper_bound(times.begin(), times.end(), r) - 1得到右端点对应的离散化下标 R。它的含义是最后一个不超过 r 的询问时刻。如果 L R说明确实有询问时刻落在 [l, r] 内把这条边插入以离散化下标构成的区间 [L, R] 上。这里有一个细节值得说如果一条边的存活区间没有覆盖到任何实际询问时刻那它对答案没有任何贡献应当直接忽略。另外一个坑是 L、R 都采用闭区间语义因为边在端点时刻 l 和 r 本身是存在的。3.3 遍历时间线段树并回滚DFS 函数的结构是这样void dfs(int o, int l, int r, vectorint ans) { int snap dsu.snapshot(); for (const Edge e : seg[o]) dsu.merge(e.u, e.v); if (l r) { for (const Query qu : asks[l]) { ans[qu.id] dsu.connected(qu.u, qu.v); } } else { int mid (l r) 1; dfs(o 1, l, mid, ans); dfs(o 1 | 1, mid 1, r, ans); } dsu.rollbackTo(snap); }进入函数时先取得当前操作栈长度 snap然后加入当前节点上的所有边处理查询或递归孩子最后统一回滚到 snap。这种“快照式回滚”是最稳的因为 merge 时如果两个点已经在同一个连通块里并不会往栈里压入任何操作。如果简单地按“进入节点时 merge 了几条边就回滚几次”来弹出merge 没真正合并的那几条会白白多弹掉正确的操作程序直接崩。3.4 完整代码下面给出一个可以完整运行的 C17 实现适合直接抠下来当模板。代码里我加了必要的注释方便对照前文思路阅读。#include bits/stdc.h using namespace std; const int MAXN 100005; struct Edge { int u, v; }; struct Query { int u, v, id; }; vectorEdge seg[MAXN 2]; vectorQuery asks[MAXN]; struct RollbackDSU { int fa[MAXN], sz[MAXN]; struct Op { int x, fax; int y, szy; }; vectorOp stk; void init(int n) { for (int i 1; i n; i) { fa[i] i; sz[i] 1; } stk.clear(); } int find(int x) { while (fa[x] ! x) x fa[x]; return x; } void merge(int a, int b) { int ra find(a), rb find(b); if (ra rb) return; if (sz[ra] sz[rb]) swap(ra, rb); stk.push_back({ra, fa[ra], rb, sz[rb]}); fa[ra] rb; sz[rb] sz[ra]; } int snapshot() { return (int)stk.size(); } void rollbackTo(int snap) { while ((int)stk.size() snap) { Op op stk.back(); stk.pop_back(); fa[op.x] op.fax; sz[op.y] op.szy; } } bool connected(int a, int b) { return find(a) find(b); } } dsu; void insertEdge(int o, int l, int r, int ql, int qr, const Edge e) { if (ql l r qr) { seg[o].push_back(e); return; } int mid (l r) 1; if (ql mid) insertEdge(o 1, l, mid, ql, qr, e); if (qr mid) insertEdge(o 1 | 1, mid 1, r, ql, qr, e); } void dfs(int o, int l, int r, vectorint ans) { int snap dsu.snapshot(); for (const Edge e : seg[o]) dsu.merge(e.u, e.v); if (l r) { for (const Query qu : asks[l]) { ans[qu.id] dsu.connected(qu.u, qu.v); } } else { int mid (l r) 1; dfs(o 1, l, mid, ans); dfs(o 1 | 1, mid 1, r, ans); } dsu.rollbackTo(snap); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n m q; vectortupleint, int, int, int edges; for (int i 0; i m; i) { int u, v, l, r; cin u v l r; edges.push_back({u, v, l, r}); } vectorint times; vectortupleint, int, int queries; for (int i 0; i q; i) { int t, u, v; cin t u v; queries.push_back({t, u, v}); times.push_back(t); } sort(times.begin(), times.end()); times.erase(unique(times.begin(), times.end()), times.end()); int T (int)times.size(); dsu.init(n); for (auto [u, v, l, r] : edges) { int L lower_bound(times.begin(), times.end(), l) - times.begin(); int R upper_bound(times.begin(), times.end(), r) - times.begin() - 1; if (L R) { insertEdge(1, 1, T, L 1, R 1, {u, v}); } } for (int i 0; i q; i) { auto [t, u, v] queries[i]; int p lower_bound(times.begin(), times.end(), t) - times.begin() 1; asks[p].push_back({u, v, i}); } vectorint ans(q, 0); if (T 0) dfs(1, 1, T, ans); for (int i 0; i q; i) { cout (ans[i] ? Yes : No) \n; } return 0; }注意这里线段树都按下标从 1 开始处理。离散化后的时间点下标从 0 开始插入线段树时统一 1避免边界情况绕晕。3.5 用样例验证一遍用第 1.2 节的样例times为 [1, 3, 4]T 3。边 1区间 [1, 3]L 0R 1插入 [1, 2]即覆盖时刻 1 和 3。边 2区间 [2, 4]L 1R 2插入 [2, 3]覆盖时刻 3 和 4。边 3区间 [1, 2]L 0R 0插入 [1, 1]只覆盖时刻 1。DFS 的过程中叶子 1时刻 1加入边 3同时祖先节点覆盖区间较大的节点上还挂着边 1。1 和 3 直接相连答案 Yes。叶子 2时刻 3边 1 和边 2 都会被加入1—2—3 连通答案 Yes。叶子 3时刻 4只有边 21 和 3 不连通答案 No。和手算结果一致。4. 比赛中常踩的坑与调试技巧4.1 回滚与节点边数不一致的两类事故第一类事故是我自己踩过的每个节点存了多少条边退出时就 rollback 多少次。表面看起来合理但一旦某条边的两个端点已经在同一个连通块里merge 函数根本不会往栈里写入任何操作。如果退出时依然按边的数目回滚就会把不属于当前节点的操作弹出导致兄弟分支的并查集现场被污染之后所有答案都可能乱掉。正确做法是进入节点时记录一下快照snap dsu.snapshot()函数退出时rollbackTo(snap)。这样无论当前节点的 merge 真正改了多少次数据结构都能准确地回到进入前的状态。凡是线段树分治相关代码我都建议只使用快照式回滚不要自作聪明地去数操作数。第二类事故是 Op 里记录的信息不够。回滚需要把被修改的所有变量都还原。上面代码里修改了fa[ra]和sz[rb]所以 Op 结构里记录的是这两个变量在修改前的值而不是只记录一个 ra。有些写法会只记录fa[ra]旧值但忘了恢复sz[rb]结果回滚后秩变得越来越大复杂度分析直接失效运气不好还会越跑越慢。4.2 离散化边界把你坑到自闭这个坑特别隐蔽。假设times只有 [1, 3, 4]一条边的区间是 [2, 5]。直观上它应该覆盖时刻 3 和 4。用lower_bound求 L 时第一个不小于 2 的时间是 3下标 1用upper_bound求 R 时第一个大于 5 的不存在是 end 下标 3减 1 得到 2对应时刻 4。所以插入 [2, 3]离散化后从 1 开始的下标恰好覆盖时刻 3 和 4。但如果把左端点写成upper_bound或者右端点也写成lower_bound边界就会偏一位导致时刻 3 这条边没加进去或者时刻 4 被漏掉。更隐蔽的是一条边区间可能完全落在两个询问时刻之间比如 times 是 [1, 3, 4]而边区间是 [0, 0] 或者 [7, 9]。这时 L 可能等于 0而 R 是 -1或者 L 是 3R 是 2判断L R直接跳过即可不要试图对负数下标做线段树插入。4.3 对拍与数据生成器写法建议任何线段树分治的题写完都写一个暴力去对拍。暴力思路对于每个询问枚举所有边判断当前时刻 t 是否落在 [l, r] 内把合法的边加进一个临时并查集然后回答连通性。数据量很小的时候这就是标准答案。数据生成器要注意几点点的编号在 1 到 n 之间边的区间 l r询问时刻 t 最好在一个受控的小范围内取值比如 1 到 10这样更容易制造多个询问共享同一时刻的情况也能覆盖测试离散化去重逻辑。我写对拍脚本时通常让它随机生成 200 组小数据每组 n, m, q 在 5 到 8 之间边和询问数量也在个位数跑几千次不出错代码基本就可以放心提交了。调试的时候还有一个小技巧在 DFS 函数的入口和出口打印当前线段树区间编号、并查集栈大小、以及关键边加入后的连通状态。虽然输出会很多但小数据下足够把问题定位到具体某个节点。如果发现某个叶子节点的查询和暴力答案不一致就优先检查该叶子节点路径上到底加入了哪些边是不是挂错了节点。4.4 这个套路还能做哪些题线段树分治 可撤销并查集不是只能做这一道题。它本质上解决的是“支持区间加边、单点时刻查询连通性”的问题所以很多看起来完全不同的题目都能套这个框架动态图连通性的离线版本。对边按存活区间给出查询某个时间点或某个历史版本里两点是否连通。带删除的连通块数量统计。可以给每条边一个出现区间然后在线段树 DFS 过程中维护当前连通块数量或者统计每个时刻的最小生成树权值之和。与二分图判定结合。把可撤销并查集扩展成带权并查集维护二分图奇偶性边权表示两个端点是否异色。这类题目在区间加边、单点时刻判二分图的场景中非常常见。背包类问题如果满足“物品只在某个时间区间可用”也可以用这个框架配合回滚式 DP 处理只不过这时回滚的数据结构不是并查集而是一个可回滚的数组原理完全一致。记得有一次比赛里遇到一道“历史版本加边、询问两点连通”的题当时我第一反应是写可持久化并查集代码长而且容易写崩。后来换回线段树分治复杂度一样自己用上面这套模板十几分钟就写完最后还顺手改成了判二分图的版本。从那以后我再看到“区间生效的边 时刻查询连通性”这类模型第一反应一定是往离线分治上想而不是直接莽在线数据结构。我个人在实际操作中的体会是线段树分治的模板不难背真正难的是把题面里的时间条件干净利落地映射成区间的开闭语义以及在实际调试时不慌不乱地检查回滚逻辑。建议第一次学的人不要急着抄完整代码先自己手动模拟一遍样例的 DFS 过程把“进入节点、加边、查询、回滚”四个动作在纸面上走通再回来写代码遇到 bug 时心里就会清楚很多。