https://www.zybuluo.com/ysner/note/1253722
定义
允许恢复历史状态的并查集。
建立
建(Q)棵主席树，每个主席树上维护当前状态并查集各个节点的父亲。
（实际上就是并查集和主席树强行捆绑在一起）
操作
每次操作前自动继承上次操作后的状态。
-
合并(a,b)所在集合
把两棵主席树按秩合并（深度大的合并到深度小的）。
如果两棵主席树合并时深度相等，给合并后的主席树深度(+1)（要不然哪来的秩） -
回到第(k)次操作之后的状态
把当前主席树的根赋值为第(k)棵主席树的即可。 -
询问(a),(b)是否属于同一集合
并查集（主）+主席树（辅）查询两者祖先，比较是否相等。
用途
- (bzoj)上刷(AC)量
- ？？？
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls t[x][0]
#define rs t[x][1]
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e6+100;
int n,m,rt[N],tot,f[N],t[N][2],d[N];
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void Build(re int &x,re int l,re int r)
{
x=++tot;
if(l==r) {f[x]=l;return;}
re int mid=l+r>>1;
Build(ls,l,mid);Build(rs,mid+1,r);
}
il void Modify(re int &x,re int las,re int l,re int r,re int pos,re int ff)
{
x=++tot;
if(l==r) {f[x]=ff;d[x]=d[las];return;}
re int mid=l+r>>1;
ls=t[las][0];rs=t[las][1];
if(pos<=mid) Modify(ls,t[las][0],l,mid,pos,ff);
else Modify(rs,t[las][1],mid+1,r,pos,ff);
}
il int Query(re int x,re int l,re int r,re int pos)
{
if(l==r) return x;
re int mid=l+r>>1;
if(pos<=mid) return Query(ls,l,mid,pos);
else return Query(rs,mid+1,r,pos);
}
il void add(re int x,re int l,re int r,re int pos)
{
if(l==r) {++d[x];return;}
re int mid=l+r>>1;
if(pos<=mid) add(ls,l,mid,pos);
else add(rs,mid+1,r,pos);
}
il int find(re int rt,re int x)
{
re int fa=Query(rt,1,n,x);
return x==f[fa]?fa:find(rt,f[fa]);
}
int main()
{
n=gi();m=gi();
Build(rt[0],1,n);
fp(i,1,m)
{
re int op=gi();
if(op==1)
{
rt[i]=rt[i-1];
re int x=find(rt[i],gi()),y=find(rt[i],gi());
if(f[x]==f[y]) continue;
if(d[x]>d[y]) swap(x,y);
Modify(rt[i],rt[i-1],1,n,f[x],f[y]);
if(d[x]==d[y]) add(rt[i],1,n,f[y]);
}
if(op==2) rt[i]=rt[gi()];
if(op==3)
{
rt[i]=rt[i-1];
re int x=find(rt[i],gi()),y=find(rt[i],gi());
puts(f[x]==f[y]?"1":"0");
}
}
return 0;
}