可撤销并查集与线段树分治：在时间维度处理动态连通性

核心洞察：当在线维护太难，不妨把时间展开。把一条边的存在视为一个区间，动态连通性就能被分治成可回滚的静态状态。 有一张设备拓扑图，链路会加入、删除，期间不断询问两个节点是否仍然连通。普通并查集擅长“只加边”：合并后父节点结构被压缩，删除一条边却没有办法知道应该拆开谁。

为什么不能直接路径压缩

路径压缩会修改沿途多个父指针。为了回滚一次合并，你必须准确恢复所有被压缩节点，这使修改记录复杂且代价高。可撤销并查集保留按秩合并，但不做路径压缩；每次合并只记录有限个改变，回滚便能按栈恢复。

struct RollbackDSU {
    vector<int> parent, size;
    vector<pair<int, int>> history;

    int find(int x) { return parent[x] == x ? x : find(parent[x]); }
    int snapshot() const { return (int)history.size(); }
};

find 因此是 O(log n) 量级，而不是近似常数；这是为了获得可逆性而主动交换的成本。

一条边在何时存在

给每次加边记录开始时间，删除时得到结束时间 [l, r)。将这条边挂到时间线段树中所有被其区间完全覆盖的节点。遍历到某个线段树节点时，挂在这里的边在该时间段内始终存在，可以安全合并。 递归进入节点前保存快照；处理完子区间后回滚到该快照。这样，左子树的合并不会污染右子树。