Rockdu's Blog

原题:

 可持久化并查集

Description

Sample Input

Sample Output

         无语了,第一次接触可持久化数据结构，好端端一个并查集写了一天。

主要问题出在可持久化线段树上面。要注意初值设置和插入函数不能出错

，否则错误特别奇葩。贴一段小小的代码

#include<cstdio>  
using namespace std;  
const int maxn=2e4+100;  
namespace Segtree{  
    struct node {  
        int l,r,ch[2],fa;  
    }tree[maxn*100];  
    int cnt=0;  
    int root[maxn],rtcnt=0;  
    void build(int l,int r,int rt){  
        tree[rt].l=l;tree[rt].r=r;  
        tree[rt].ch[0]=++cnt;tree[rt].ch[1]=++cnt;  
        if(l==r)    {tree[rt].fa=l;return;}  
        int mid=(l+r)/2;  
        build(l,mid,tree[rt].ch[0]);  
        build(mid+1,r,tree[rt].ch[1]);  
    }  
    int query(int pos,int rt){  
        int tl=tree[rt].l,tr=tree[rt].r;  
        if(tl==tr) return tree[rt].fa;  
        int mid=(tl+tr)/2;  
        if(pos<=mid) return query(pos,tree[rt].ch[0]);  
        else return query(pos,tree[rt].ch[1]);  
    }  
    void update(int num,int &rt,int pos){  
        tree[++cnt]=tree[rt],rt=cnt;  
        int tl=tree[rt].l,tr=tree[rt].r;  
        if(tl==tr) {tree[rt].fa=num;return;}  
        int mid=(tl+tr)/2;  
        if(pos<=mid) update(num,tree[rt].ch[0],pos);  
        else update(num,tree[rt].ch[1],pos);  
    }  
}  
  
namespace comset{  
    using namespace Segtree;  
    void init(int n){root[0]=rtcnt=cnt=0;build(1,n,0);}  
    int find(int x){  
        int fa=query(x,root[rtcnt]);  
        if(fa==x) return x;  
        return find(fa);  
    }  
    void combine(int a,int b){  
        a=find(a),b=find(b);  
        root[rtcnt+1]=root[rtcnt++];  
        update(b,root[rtcnt],a);  
    }  
    void back(int k){  
        root[++rtcnt]=root[k];  
    }  
}  
  
int main(){  
    using namespace comset;  
    int n,m;  
    scanf("%d%d",&n,&m);  
    init(n);  
    for(int i=1;i<=m;i++){  
        int opt,a,b;  
        scanf("%d",&opt);  
        if(opt==1)  scanf("%d%d",&a,&b),combine(a,b);  
        if(opt==2)  scanf("%d",&a),back(a);  
        if(opt==3)  scanf("%d%d",&a,&b),root[rtcnt+1]=root[rtcnt++],printf("%d\n",find(a)==find(b)?1:0);  
    }  
    return 0;  
}