BZOJ 3673 可持久化并查集 by zky

Description

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

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

可持久化并查集不好写，我们考虑到并查集的写法就是查找父亲节点，修改父亲节点的指向，单点查询和修改，我们就可以用主席树来对它进行维护

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5;
int root[N+100],val[N*20+100],ls[N*20+100],rs[N*20+100];
int cnt,n,m;
int read(){
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())    x=x*10+ch-'0';
    return x*f;
}
void build(int &k,int l,int r){
    k=++cnt;
    if (l==r){val[k]=l;return;}
    int mid=(l+r)>>1;
    build(ls[k],l,mid);
    build(rs[k],mid+1,r);
}
int get(int k,int l,int r,int x){
    if (l==r)   return val[k];
    int mid=(l+r)>>1;
    if (x<=mid) return get(ls[k],l,mid,x);
    else    return get(rs[k],mid+1,r,x);
}
void Add(int &k,int p,int l,int r,int x,int t){
    k=++cnt;
    ls[k]=ls[p]; rs[k]=rs[p];
    if (l==r){val[k]=t;return;}
    int mid=(l+r)>>1;
    if (x<=mid) Add(ls[k],ls[p],l,mid,x,t);
    else    Add(rs[k],rs[p],mid+1,r,x,t);
}
int find(int k,int x){
    int tmp=get(k,1,n,x);
    if (tmp==x) return x;
    int ans=find(k,tmp);
    Add(k,k,1,n,x,ans);
    return ans;
}
int main(){
    n=read(),m=read();
    build(root[0],1,n);
    for (int i=1;i<=m;i++){
        int t=read();
        if (t==1){
            int x=read(),y=read();
            int fx=find(root[i-1],x),fy=find(root[i-1],y);
            if (fx==fy) root[i]=root[i-1];
            else    Add(root[i],root[i-1],1,n,fx,fy);
        }
        if (t==2){
            int x=read();
            root[i]=root[x];
        }
        if (t==3){
            int x=read(),y=read();
            int fx=find(root[i-1],x),fy=find(root[i-1],y);
            if (fx==fy) printf("1\n");
            else    printf("0\n");
            root[i]=root[i-1];
        }
    }
    return 0;
}