可持久化并查集

#include <iostream>
using namespace std;
const int maxn = 2e5+5;
int n;
struct Node{
    int l,r,val;
};
Node tree[maxn*40*2];
int cnt, rootfa[maxn], rootdep[maxn], tot;
void build(int l, int r, int &now)
{
    now = ++cnt;
    if(l == r)
    {
        tree[now].val = ++tot;
        return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, tree[now].l);
    build(mid+1, r, tree[now].r);
}
void modify(int l, int r, int ver, int &now, int pos, int val){
    tree[now = ++cnt] = tree[ver];
    if(l == r)
    {
        tree[now].val = val;
        return;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) modify(l, mid, tree[ver].l, tree[now].l, pos, val);
    else modify(mid+1, r, tree[ver].r, tree[now].r, pos, val);
}
int query(int l, int r, int now, int pos){
    if(l == r) return tree[now].val;
    int mid = (l+r) >> 1;
    if(pos <= mid) return query(l, mid, tree[now].l, pos);
    else return query(mid+1, r, tree[now].r, pos);
}
int find(int ver, int x){
    int fx = query(1, n, rootfa[ver], x);
    return fx == x? x: find(ver, fx);
}
void merge(int ver, int x, int y)
{
    x = find(ver-1, x);
    y = find(ver-1, y);
    if(x == y){
        rootfa[ver] = rootfa[ver-1];
        rootdep[ver] = rootdep[ver-1];
    }else{
        int depx = query(1,n,rootdep[ver-1],x);
        int depy = query(1,n,rootdep[ver-1],y);
        if(depx > depy)  swap(x, y), swap(depx, depy);
        modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
        if(depx == depy)    modify(1,n,rootdep[ver-1],rootdep[ver],y,depy+1);
        else    rootdep[ver]=rootdep[ver-1];
    }
}