[文章目录]
Descritption
n个集合 m个操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0
0 < n,m < =2 * 10^5
可持久化线段树维护可持久化数组，进而维护按秩合并的并查集。
合并的时候，每次查询一次fa[x]时间logn，查询log次，按秩合并后修改辅助度logn。总时间复杂度O(nlog^2n)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
struct seg
{
int ls,rs,w,siz;
}t[13000000];
int rot[201000],se;
int build(int l,int r)
{
int re=++se;
if(l==r)
{
t[re].w=l; t[re].siz=1;
return re;
}
int mid=(l+r)>>1;
t[re].ls=build(l,mid);
t[re].rs=build(mid+1,r);
return re;
}
void insert(int &p1,int p2,int l,int r,int x,int y,int z)
{
p1=++se;
if(l==r) {t[p1].w=y; t[p1].siz=z; return;}
int mid=(l+r)>>1;
if(x<=mid) t[p1].rs=t[p2].rs,insert(t[p1].ls,t[p2].ls,l,mid,x,y,z);
else t[p1].ls=t[p2].ls,insert(t[p1].rs,t[p2].rs,mid+1,r,x,y,z);
}
int query(int p,int l,int r,int x)
{
if(l==r) return p;
int mid=(l+r)>>1;
if(x<=mid) return query(t[p].ls,l,mid,x);
else return query(t[p].rs,mid+1,r,x);
}
int main()
{
scanf("%d%d",&n,&m);
rot[0]=build(1,n);
int x,y,sw,now=0,k,p,ans=0;
while(m--)
{
scanf("%d",&sw);
++now; rot[now]=rot[now-1];
if(sw==1)
{
scanf("%d%d",&x,&y); x^=ans; y^=ans;
p=query(rot[now],1,n,x);
while(x!=t[p].w) x=t[p].w,p=query(rot[now],1,n,x);
x=p;
p=query(rot[now],1,n,y);
while(y!=t[p].w) y=t[p].w,p=query(rot[now],1,n,y);
y=p;
if(x!=y)
{
if(t[x].siz>t[y].siz) swap(x,y);
insert(rot[now],rot[now],1,n,t[y].w,t[y].w,t[x].siz+t[y].siz);
insert(rot[now],rot[now],1,n,t[x].w,t[y].w,0);
}
}
else if(sw==2) {scanf("%d",&k); k^=ans; rot[now]=rot[k];}
else
{
scanf("%d%d",&x,&y); x^=ans; y^=ans;
p=query(rot[now],1,n,x);
while(x!=t[p].w) x=t[p].w,p=query(rot[now],1,n,x);
p=query(rot[now],1,n,y);
while(y!=t[p].w) y=t[p].w,p=query(rot[now],1,n,y);
if(x==y) ans=1,puts("1");
else ans=0,puts("0");
}
}
return 0;
}