题解

思路

每次操作完成后都形成一个版本。合并只会改变两个根节点中的一个父亲，秩相等时再改变另一个根的秩，因此可以用可持久化线段树保存每个元素在各版本中的父亲和秩。

做法

初始版本的叶子 $i$ 保存父亲 $i$、秩零。查询某元素的父亲时在线段树中定位对应叶子；沿父亲不断查询即可找到集合代表元。为了保证查找链较短，合并时按秩合并，但不能做路径压缩，因为路径压缩会同时修改许多旧版本共享的节点。

操作 1 从上一个版本出发，对较低秩根的父亲做一次可持久化单点修改；秩相等时再对新根的秩做一次修改。操作 2 直接令当前根指针等于第 $k$ 个版本的根。操作 3 继承上一个版本，比较两个代表元并输出结果。

小规模可完整复制每个版本的父亲与秩数组；没有回退时可直接使用普通并查集。

复杂度

按秩合并使并查集树高为 $O(\log n)$，每次父亲查询或修改在线段树中耗时 $O(\log n)$，因此单次操作最坏为 $O(\log^2 n)$，空间复杂度为 $O(n+m\log n)$。

正确性证明

初始版本中每个元素的父亲是自身，与初始集合一致。对任一版本，假设线段树保存的父亲和秩与该版本并查集一致：合并操作先找出两个真实根，若不同则按秩只修改应连接根的父亲，并在秩相等时增加新根秩，所得状态正是并查集合并结果；回退直接复用目标版本根指针，完全恢复该状态；查询不改变状态，两个元素代表元相同当且仅当它们属于同一集合。归纳可知所有版本及查询答案均正确。