bzoj 3673&3674: 可持久化并查集 by zky

Description

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

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

Input

Output

Sample Input

5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

Sample Output

1
0
1

题解：

首先普通并查集操作中，是靠fa这个数组维护的

所以要可持久并查集，就要可持久化fa数组，所以用到可持久化线段树维护.

注意要路径压缩

 #include <algorithm>
 #include <iostream>
 #include <cstdlib>
 #include <cstring>
 #include <cstdio>
 #include <cmath>
 #define RG register
 #define il inline
 using namespace std;
 const int N=,M=;
 int gi(){
     int str=;char ch=getchar();
     while(ch>'' || ch<'')ch=getchar();
     while(ch>='' && ch<='')str=(str<<)+(str<<)+ch-,ch=getchar();
     return str;
 }
 int n,m,tot=,root[M];
 struct node{
     int ls,rs,fa;
 }t[N];
 il void build(int &rt,int l,int r){
     rt=++tot;
     if(l==r){
         t[rt].fa=l;
         return ;
     }
     int mid=(l+r)>>;
     build(t[rt].ls,l,mid);build(t[rt].rs,mid+,r);
 }
 il int query(int rt,int l,int r,int sa){
     if(l==r)
         return rt;
     int mid=(l+r)>>;
     if(sa>mid)return query(t[rt].rs,mid+,r,sa);
     else return query(t[rt].ls,l,mid,sa);
 }
 il void updata(int &rt,int last,int l,int r,int sa,int to){
     rt=++tot;t[rt]=t[last];
     if(l==r){
         t[rt].fa=to;
         return ;
     }
     int mid=(l+r)>>;
   if(sa>mid)updata(t[rt].rs,t[last].rs,mid+,r,sa,to);
     else updata(t[rt].ls,t[last].ls,l,mid,sa,to);
 }
 il int find(int x,int i){
     int c=query(root[i],,n,x);
     if(t[c].fa==x)return x;
     int d=find(t[c].fa,i);
     updata(root[i],root[i],,n,x,d);
     return d;
 }
 void work()
 {
     int flag,x,y,fx,fy;
     n=gi();m=gi();
     build(root[],,n);
     for(int i=;i<=m;i++){
         flag=gi();x=gi();
         if(flag==){
             y=gi();
             root[i]=root[i-];
             fx=find(x,i);fy=find(y,i);
             if(fx==fy)continue;
             updata(root[i],root[i-],,n,fx,fy);
         }
         else if(flag==)root[i]=root[x];
         else{
             y=gi();
             root[i]=root[i-];
             fx=find(x,i);fy=find(y,i);
             if(fx==fy)puts("");
             else puts("");
         }
     }
 } int main()
 {
     work();
     return ;
 }