可持久化并查集
<pre><code class="language-cpp">#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];
}
}</code></pre>