考虑并查集的过程，\(fa_x=y\) 仿佛是不可逆的。你考虑这是一个赋值，且每次操作只会实行一次（usually），发现这可以可持久化。于是用主席树维护这个 \(fa\) 即可。
但由于你直接跳 \(fa\) 是 \(\mathcal {O}(n)\)，又不能改变 \(fa\) 的形态，于是只能用按秩合并，然后查根是 \(\mathcal{O}(log_2^2 n)\) 的。板子：
#include
#include
#include
#include
#include
#define ls tree[p].L
#define rs tree[p].R
using namespace std;
const int MAXN = 2e5 + 5;
struct Node {
int L, R;
}tree[MAXN * 25];
int n, m, now, root[MAXN], dep[MAXN * 25], fa[MAXN * 25], tot;
int ask(int p, int l, int r, int x) { // 查询位置 x在时态 t下对应线段树的编号
if(l == r) return p;
int mid = (l + r) >> 1; return x <= mid ? ask(ls, l, mid, x) : ask(rs, mid + 1, r, x);
}
void build(int &p, int l, int r) { // 建好树，弄好 dep,fa
p = ++ tot;
if(l == r) { dep[p] = 1; fa[p] = l; return; }
int mid = (l + r) >> 1; build(ls, l, mid); build(rs, mid + 1, r);
}
int fnd(int x) { int p = ask(root[now], 1, n, x); return fa[p] ^ x ? fnd(fa[p]) : x; } // x 为实际编号, p 为 smt对应的编号
void add(int &p, int q, int l, int r, int x, int y, int f) {
if(!f) p = ++ tot, tree[p] = tree[q], dep[p] = dep[q], fa[p] = fa[q]; // 注意 dep,fa 也要搞过来
// 另外加上 !f 卡常(基本少建 1/2的点)
if(l == r) {
if(!f) fa[p] = y;
else dep[p] = y;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) add(ls, tree[q].L, l, mid, x, y, f);
else add(rs, tree[q].R, mid + 1, r, x, y, f);
}
void makefa(int u, int v, int p, int q) { // u,v 下标 p,q 对应编号
int r = dep[p] == dep[q] ? dep[q] + 1 : dep[q];
now ++; add(root[now], root[now - 1], 1, n, u, v, 0); add(root[now], root[now], 1, n, v, r, 1);
}
void mrg(int x, int y) {
int u = fnd(x), v = fnd(y);
if(u == v) { now ++; root[now] = root[now - 1]; return; } // 注意这里 root 也要搞过来
int p = ask(root[now], 1, n, u), q = ask(root[now], 1, n, v);
if(dep[p] <= dep[q]) makefa(u, v, p, q);
else makefa(v, u, q, p);
}
int main() {
int f, l, r, x; scanf("%d%d", &n, &m); build(root[0], 1, n);
for(int i = 1; i <= m; i ++) {
scanf("%d", &f);
if(f == 1) scanf("%d%d", &l, &r), mrg(l, r);
else if(f == 2) scanf("%d", &x), root[++ now] = root[x];
else now ++, root[now] = root[now - 1], scanf("%d%d", &l, &r), printf("%d\n", fnd(l) == fnd(r));
}
return 0;
}
好，既然你已经学会了可持久化并查集了，让我们来看一道 例题（NOI2018 归程） 吧。
考虑如果可以连离线，我们可以按照询问的水位高度排序，顺序处理，维护一个并查集即可。
那这个在线，肯定就想到可持久化并查集，离散化后把水位作为时间即可。当然并查集的时候要有权值的更新，具体地也不难搞。
然后这里有一个卡常技巧是对于一个时间，新建的点只用建一次，剩下的直接更新即可。具体看代码。
#include
#include
#include
#include
#include
#include