【可持久化并查集】BZOJ3673-可持久化并查集 by zky

颓了十多天别问我再干嘛，在补学校作业

啊，开学了……我的夏天……

【题目大意】

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

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

【思路】

数组是可以利用线段树的形式可持久化的，方法和主席树一模一样。那么我们在可持久化数组的基础上加上并查集的操作就可以了。

每次合并操作，先查询要合并两个元素的父亲所在位置。方法是如果当前位置的v不等于它所代表的数组中的下标（不是当前下标），那么就继续find。其余操作并查集没有区别。

回到k次状态只要T[0]=T[k]即可。

查询是否属于一个集合也是找出父亲，直接判断即可，同并查集。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define lson l,m
  6 #define rson m+1,r
  7 const int MAXN=325754;
  8 using namespace std;
  9 int T[MAXN],v[MAXN],h[MAXN],L[MAXN],R[MAXN];
 10 int cnt,m,n;
 11 
 12 int build(int l,int r)
 13 {
 14     int rt=++cnt;
 15     if (l==r) v[rt]=l;
 16     else
 17     {
 18         int m=(l+r)>>1;
 19         L[rt]=build(lson);
 20         R[rt]=build(rson);
 21     }
 22     return rt;
 23 }
 24 
 25 int query(int rt,int x,int l,int r)
 26 {
 27     if (l==r) return rt;
 28     int m=(l+r)>>1;
 29     if (x<=m) return query(L[rt],x,lson);
 30         else return query(R[rt],x,rson);
 31 }
 32 
 33 int find(int rt,int x)
 34 {
 35     int p=query(rt,x,1,n);
 36     if (x==v[p]) return p;
 37         else return find(rt,v[p]);
 38 }
 39 
 40 void update(int rt,int x,int l,int r)
 41 {
 42     if (l==r)
 43     {
 44         h[rt]++;
 45         return;
 46     }
 47     int m=(l+r)>>1;
 48     if (x<=m) update(L[rt],x,lson);
 49         else update(R[rt],x,rson);
 50 }
 51 
 52 int modify(int pre,int x,int y,int l,int r)
 53 {
 54     int rt=++cnt;
 55     if (l==r)
 56     {
 57         v[rt]=y;
 58         h[rt]=h[pre];//不要忘了秩 
 59         return rt;
 60     }
 61     L[rt]=L[pre],R[rt]=R[pre];
 62     int m=(l+r)>>1;
 63     if (x<=m) L[rt]=modify(L[pre],x,y,lson);
 64         else R[rt]=modify(R[pre],x,y,rson);
 65     return rt;
 66 }
 67 
 68 void union_set(int fa,int fb,int i)
 69 {
 70     if (h[fa]>h[fb]) swap(fa,fb);
 71     T[i]=modify(T[i-1],v[fa],v[fb],1,n);//注意这里是v[fa]而不是fa 
 72     if (h[fa]==h[fb]) update(T[i],v[fb],1,n);
 73 }
 74 
 75 void init()
 76 {
 77     cnt=0;
 78     scanf("%d%d",&n,&m);
 79     T[0]=build(1,n);
 80 }
 81 
 82 void solve()
 83 {
 84     for (int i=1;i<=m;i++)
 85     {
 86         int op,a,b;
 87         scanf("%d",&op);
 88         if (op==1)
 89         {
 90             scanf("%d%d",&a,&b);
 91             T[i]=T[i-1];
 92             int fa=find(T[i],a),fb=find(T[i],b);
 93             if (v[fa]!=v[fb]) union_set(fa,fb,i);
 94         }
 95         if (op==2)
 96         {
 97             scanf("%d",&a);
 98             T[i]=T[a];
 99         }
100         if (op==3)
101         {
102             scanf("%d%d",&a,&b);
103             T[i]=T[i-1];
104             int fa=find(T[i],a),fb=find(T[i],b);
105             if (v[fa]==v[fb]) puts("1");else puts("0");
106         }
107     }
108 }
109 
110 int main()
111 {
112     init();
113     solve(); 
114     return 0;
115 }