题目：bzoj3673：https://www.lydsy.com/JudgeOnline/problem.php?id=3673
bzoj3674：https://www.lydsy.com/JudgeOnline/problem.php?id=3674
洛谷P3402：https://www.luogu.org/problemnew/show/P3402
可持久化并查集！就是用主席树模拟并查集，真美！
路径压缩版：和并查集的相似之处想想感觉好妙；
但复杂度似乎有点不科学，bzoj 的两道题都能过，但洛谷上的模板过不了；
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=2e4+,maxm=3e6+;
//int const maxn=2e5+5,maxm=1e7+5;
int n,m,f[maxm],ls[maxm],rs[maxm],rt[maxn],cnt,ans;
void build(int &x,int l,int r)
{
x=++cnt;
if(l==r){f[x]=l; return;}
int mid=((l+r)>>);
build(ls[x],l,mid); build(rs[x],mid+,r);
}
void insert(int x,int &y,int l,int r,int pos,int val)
{
y=++cnt;
if(l==r){f[y]=val; return;}//不是f[pos]
int mid=((l+r)>>);
ls[y]=ls[x]; rs[y]=rs[x];
if(pos<=mid)insert(ls[x],ls[y],l,mid,pos,val);
else insert(rs[x],rs[y],mid+,r,pos,val);
}
int query(int x,int l,int r,int pos)
{
if(l==r)return f[x];
int mid=((l+r)>>);
if(pos<=mid)return query(ls[x],l,mid,pos);
else return query(rs[x],mid+,r,pos);
}
int find(int &root,int pos)
{
int tmp=query(root,,n,pos);
if(tmp==pos)return pos;
int ret=find(root,tmp);
insert(root,root,,n,pos,ret);//路径压缩，修改root
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
build(rt[],,n);
for(int i=,op,k,x,y;i<=m;i++)
{
scanf("%d",&op);
if(op==)
{
scanf("%d%d",&x,&y);
// x^=ans; y^=ans;
int fx=find(rt[i-],x),fy=find(rt[i-],y);
if(fx==fy)rt[i]=rt[i-];
else insert(rt[i-],rt[i],,n,fx,fy);
}
if(op==)
{
scanf("%d",&k);
// k^=ans;
rt[i]=rt[k];
}
if(op==)
{
scanf("%d%d",&x,&y);
// x^=ans; y^=ans;
int fx=find(rt[i-],x),fy=find(rt[i-],y);
if(fx==fy)ans=,printf("1\n");
else ans=,printf("0\n");
rt[i]=rt[i-];
}
}
return ;
}
按秩合并版：复杂度科学，写起来也很简洁，洛谷模板能过；
感觉数据结构写好了模板摆在那儿什么都能干，很方便啊。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=2e5+,maxm=1e7+;
int n,m,f[maxm],ls[maxm],rs[maxm],dep[maxm],rt[maxn],cnt,ans;
void build(int &x,int l,int r)
{
x=++cnt;
if(l==r){f[x]=l; dep[x]=; return;}
int mid=((l+r)>>);
build(ls[x],l,mid); build(rs[x],mid+,r);
}
void insert(int x,int &y,int l,int r,int pos,int val)
{
y=++cnt;
if(l==r){f[y]=val; dep[y]=dep[x]; return;}
int mid=((l+r)>>);
ls[y]=ls[x]; rs[y]=rs[x];
if(pos<=mid)insert(ls[x],ls[y],l,mid,pos,val);
else insert(rs[x],rs[y],mid+,r,pos,val);
}
void add(int x,int &y,int l,int r,int val)
{
y=++cnt;
if(l==r){f[y]=val; dep[y]=dep[x]+; return;}
int mid=((l+r)>>);
ls[y]=ls[x]; rs[y]=rs[x];
if(val<=mid)add(ls[x],ls[y],l,mid,val);
else add(rs[x],rs[y],mid+,r,val);
}
int query(int x,int l,int r,int pos)
{
if(l==r)return x;
int mid=((l+r)>>);
if(pos<=mid)return query(ls[x],l,mid,pos);
else return query(rs[x],mid+,r,pos);
}
int find(int &root,int pos)
{
int tmp=query(root,,n,pos);
if(f[tmp]==pos)return tmp;
return find(root,f[tmp]);
}
int main()
{
scanf("%d%d",&n,&m);
build(rt[],,n);
for(int i=,op,k,x,y;i<=m;i++)
{
scanf("%d",&op);
if(op==)
{
scanf("%d%d",&x,&y);
int fx=find(rt[i-],x),fy=find(rt[i-],y);
if(f[fx]==f[fy]){rt[i]=rt[i-]; continue;}
if(dep[fx]>dep[fy])swap(fx,fy);
insert(rt[i-],rt[i],,n,f[fx],f[fy]);
if(dep[fx]==dep[fy])add(rt[i],rt[i],,n,f[fy]);//最大深度相等则合并后dep+1
}
if(op==)
{
scanf("%d",&k);
rt[i]=rt[k];
}
if(op==)
{
scanf("%d%d",&x,&y);
int fx=find(rt[i-],x),fy=find(rt[i-],y);
if(fx==fy)ans=,printf("1\n");
else ans=,printf("0\n");
rt[i]=rt[i-];
}
}
return ;
}