n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

0<n,m<=2*10^4

出题人大SB

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThornusing namespace std;const int maxn=20000+5,maxm=5000000+5;int n,m,tot,ls[maxm],rs[maxm],fa[maxm],siz[maxm],root[maxn];inline void build(int &x,int l,int r){	x=++tot;int mid=(l+r)>>1;	if(l==r){		siz[x]=1,fa[x]=l;		return;	}	build(ls[x],l,mid);build(rs[x],mid+1,r);}inline void change(int l,int r,int x,int &y,int pos,int val){	y=++tot;	if(l==r){		fa[y]=val,siz[y]=siz[x];		return;	}	int mid=(l+r)>>1;ls[y]=ls[x];rs[y]=rs[x];	if(pos<=mid)		return change(l,mid,ls[x],ls[y],pos,val);	else		return change(mid+1,r,rs[x],rs[y],pos,val); }inline void add(int l,int r,int x,int pos,int val){	if(l==r){		siz[x]+=val;		return;	}	int mid=(l+r)>>1;	if(pos<=mid)		add(l,mid,ls[x],pos,val);	else		add(mid+1,r,rs[x],pos,val);}inline int query(int l,int r,int x,int pos){	if(l==r)		return x;	int mid=(l+r)>>1;	if(pos<=mid)		return query(l,mid,ls[x],pos);	else		return query(mid+1,r,rs[x],pos);}inline int find(int rt,int x){	int f=query(1,n,rt,x);	if(fa[f]==x)		return f;	return find(rt,fa[f]);}signed main(void){	scanf("%d%d",&n,&m);build(root[0],1,n);	for(int i=1,opt,x,y;i<=m;i++){		scanf("%d",&opt);		if(opt==1){			scanf("%d%d",&x,&y);root[i]=root[i-1];			int fx=find(root[i],x),fy=find(root[i],y);			if(fa[fx]==fa[fy])				continue;			if(siz[fx]>siz[fy])				swap(fx,fy);			change(1,n,root[i-1],root[i],fa[fx],fa[fy]),add(1,n,root[i],fa[fy],siz[fx]);		}		else if(opt==2)			scanf("%d",&x),root[i]=root[x];		else{			scanf("%d%d",&x,&y),root[i]=root[i-1];			int fx=find(root[i],x),fy=find(root[i],y);			if(fa[fx]==fa[fy])				puts("1");			else				puts("0");		}	}	return 0;}