在基础并查集上改良，让并查集支持回滚到历史版本
这里介绍一下普通并查集的两种优化，一个是路径压缩，一个是按秩合并（启发式合并）
路径压缩是在find上动手脚，让查询经过的点都直接与根相连，这样下次再查的时候复杂度就可以是O（1）
按秩合并是在union上动手脚，合并时让小集合拼接到较大集合上面，集合的大小用deep来衡量，这样就可以近似得到O（logn）的复杂度
在实现可持久化的时候，加上路径压缩会慢，只需要用按秩合并优化就好了
但是对于普通并查集来说，路径压缩就已经相当快了
其实并查集就是一个fa数组，那么可持久化并查集就是让这个数组更高级一些就可以了
多高级呢？支持单点修改和历史版本查询的数组
具体的做法是开一个可持久化线段树（可持久化线段树的思想在主席树里有介绍）
这棵线段树的非叶子节点i只负责维护lson和rson，不维护除此之外的任何信息
它的作用是方便我们在修改的时候快速地将[Li,Ri]这一段O(1)地指向它的历史版本
使用启发式合并
这样找一个节点所在集合的根，就需要查询log(n)次线段树
而每一次时间都是log(n)，故时间为O(m*log^2(n))，空间为m*log(n)
1 #include2 #include 3 using namespace std; 4 const int maxn=200005; 5 const int maxm=200005; 6 int n,m,sz,last; 7 int root[maxm],lch[10000005],rch[10000005],v[10000005],deep[10000005]; 8 inline int read() 9 {10 int x=0;char ch=getchar();11 while(ch>'9'||ch<'0') ch=getchar();12 while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}13 return x;14 }15 void build(int &k,int l,int r)16 {17 if(k==0) k=++sz;18 if(l==r) {v[k]=l;return;}19 int mid=(l+r)>>1;20 build(lch[k],l,mid);21 build(rch[k],mid+1,r);22 }23 void modify(int l,int r,int x,int &y,int pos,int val)24 {25 y=++sz;26 if(l==r) {v[y]=val;deep[y]=deep[x];return;}27 lch[y]=lch[x];rch[y]=rch[x];28 int mid=(l+r)>>1;29 if(pos<=mid)30 modify(l,mid,lch[x],lch[y],pos,val);31 else modify(mid+1,r,rch[x],rch[y],pos,val);32 }33 int query(int k,int l,int r,int pos)34 {35 if(l==r) return k;36 int mid=(l+r)>>1;37 if(pos<=mid) return query(lch[k],l,mid,pos);38 else return query(rch[k],mid+1,r,pos);39 }40 void add(int k,int l,int r,int pos)41 {42 if(l==r) {deep[k]++;return;}43 int mid=(l+r)>>1;44 if(pos<=mid) add(lch[k],l,mid,pos);45 else add(rch[k],mid+1,r,pos);46 }47 int find(int k,int x)48 {49 int p=query(k,1,n,x);50 if(x==v[p]) return p;51 return find(k,v[p]);52 }53 int main()54 {55 n=read();m=read();56 build(root[0],1,n);57 int f,k,a,b;58 for(int i=1;i<=m;i++)59 {60 f=read();61 if(f==1)62 {63 root[i]=root[i-1];64 a=read();b=read();a=a^last;b=b^last;65 int p=find(root[i],a),q=find(root[i],b);66 if(v[p]==v[q]) continue;67 if(deep[p]>deep[q]) swap(p,q);68 modify(1,n,root[i-1],root[i],v[p],v[q]);69 if(deep[p]==deep[q]) add(root[i],1,n,v[q]);70 }71 if(f==2)72 {73 k=read();k=k^last;root[i]=root[k];74 }75 if(f==3)76 {77 root[i]=root[i-1];78 a=read();b=read();a=a^last;b=b^last;79 int p=find(root[i],a),q=find(root[i],b);80 if(v[p]==v[q]) last=1;81 else last=0;82 printf("%d\n",last);83 }84 }85 }
仔细观察主席树和带修主席树的代码，可以发现有的地方是一致的
这里的add是改秩