既然有了可持久化数组，就有可持久化并查集。。
由于上课讲过说是只能按秩合并（但是我也不确定。。。），所以就先写了按秩合并，相当于是维护fa[]和rk[]
getf就是在这棵树中找，直到找到一个点的fa[x]==x
之所以这种写法不能路径压缩，个人理解是因为路径压缩会破坏原先的结构。。。反正我魔改改错了。。。先咕着路径压缩qwq
下面是加强版的代码。。。只有按秩合并
#include<cstdio> #include<iostream> #define R register int #define pc(x) putchar(x) using namespace std; const int N=2E5+10,M=1E7+10; inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } int n,m,tot,lst,crt; int rt[N],ls[M],rs[M],vl[M],rk[M]; inline void build(int& tr,int l,int r) { tr=++tot; if(l==r) {vl[tr]=l,rk[tr]=1; return; } R md=l+r>>1; build(ls[tr],l,md),build(rs[tr],md+1,r); } inline void ins(int& tr,int lst,int l,int r,int pos,int v) { tr=++tot,ls[tr]=ls[lst],rs[tr]=rs[lst],vl[tr]=vl[lst],rk[tr]=rk[lst]; if(l==r) {vl[tr]=v; return ;} R md=l+r>>1; pos<=md?ins(ls[tr],ls[lst],l,md,pos,v):ins(rs[tr],rs[lst],md+1,r,pos,v); } inline int getf(int tr,int l,int r,int pos) { if(l==r) {return pos==vl[tr]?tr:getf(rt[crt],1,n,vl[tr]);} R md=l+r>>1; return (pos<=md)?getf(ls[tr],l,md,pos):getf(rs[tr],md+1,r,pos); } inline void add(int& tr,int lst,int l,int r,int pos) { tr=++tot; ls[tr]=ls[lst],rs[tr]=rs[lst],vl[tr]=vl[lst],rk[tr]=rk[lst]; if(l==r) {++rk[tr]; return ;} R md=l+r>>1; pos<=md?add(ls[tr],ls[lst],l,md,pos):add(rs[tr],rs[lst],md+1,r,pos); } signed main() { n=g(),m=g(); build(rt[0],1,n); for(R i=1;i<=m;++i) { R k=g(),a=g()^lst,b; if(k==1) { rt[i]=rt[i-1],crt=i; b=g()^lst; a=getf(rt[i],1,n,a); b=getf(rt[i],1,n,b); if(vl[a]!=vl[b]) { if(rk[a]<rk[b]) swap(a,b); ins(rt[i],rt[i-1],1,n,vl[b],vl[a]); if(rk[a]==rk[b]) add(rt[i],rt[i],1,n,vl[a]); } } else if(k==2) rt[i]=rt[a]; else { rt[i]=rt[i-1],crt=i; b=g()^lst; a=getf(rt[i],1,n,a),b=getf(rt[i],1,n,b); vl[a]==vl[b]?(lst=1,pc('1'),pc(' ')):(lst=0,pc('0'),pc(' ')); //cout<<"fasdhfjlkasdf"<<endl; } } //while(1); }
2019.05.06