JZTXT

可持久化并查集

发布时间 2023-03-23 19:39:47作者: 风月无边~windymoon

可持久化并查集

感觉就是把并查集的数组可持久化一下，本质上就是可持久化数组

并查集想到启发式合并和路径压缩，路径压缩空间可能会炸，考虑启发式合并

两个数组分别维护 \(fa\) 和 \(sz\)，每次将 \(sz\) 小的合并到 \(sz\) 大的上面，记得更新 \(sz\)

并查集部分

询问

il int up(int x,int i){
    ri int k;
    while((k=fa.ask(fa.rot[i],x))^x) x=k;
    return x;
}

合并

il void merge(int a,int b,int i){
    a=up(a,i),b=up(b,i);
    if(a^b){
        ri int sza=sz.ask(sz.rot[i],a);
        ri int szb=sz.ask(sz.rot[i],b);
        if(sza>szb) swap(sza,szb),swap(a,b);
        fa.update(i,fa.rot[i],a,b);
        sz.update(i,sz.rot[i],b,sza+szb);
    }
    return;
}

可持久化数组部分

struct arr{
    int rot[N],cnt,a[N];
    struct tre{
        int ls,rs,val;
    }t[N<<5];
    il int build(int l,int r){
        if(l>r) return 0;
        ri int rt=++cnt,mid=(l+r)>>1;
        t[rt].val=a[mid];
        t[rt].ls=build(l,mid-1);
        t[rt].rs=build(mid+1,r);
        return rt;
    }
    il void update(int id,int pre,int pos,int k){
        ri int l=1,r=n,rt=rot[id]=++cnt,mid;
        while(pre){
            t[rt]=t[pre],mid=(l+r)>>1;
            if(mid==pos) {t[rt].val=k; break;}
            if(pos<mid) r=mid-1,t[rt].ls=++cnt,pre=t[pre].ls,rt=t[rt].ls;
            else l=mid+1,t[rt].rs=++cnt,pre=t[pre].rs,rt=t[rt].rs;
        }
        return;
    }
    il int ask(int rt,int pos){
        ri int l=1,r=n,mid;
        while(rt&&l<=r){
            mid=(l+r)>>1;
            if(mid==pos) return t[rt].val;
            if(pos<mid) r=mid-1,rt=t[rt].ls;
            else l=mid+1,rt=t[rt].rs;
        }
        return 0;
    }
}fa,sz;
code 
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;

namespace Q{
    il int rd(){
        ri int x=0;ri bool f=0;ri char c=getchar();
        while(!isdigit(c)) f|=(c==45),c=getchar();
        while(isdigit(c)) x=x*10+(c^48),c=getchar();
        return f?-x:x;
    }
    il void wt(int x){
        if(x<0) x=-x,putchar(45);
        if(x>=10) wt(x/10);
        return putchar(x%10|48),void();
    }
} using namespace Q;

cs int N=1e5+1;
int n,m;

struct arr{
    int rot[N],cnt,a[N];
    struct tre{
        int ls,rs,val;
    }t[N<<5];
    il int build(int l,int r){
        if(l>r) return 0;
        ri int rt=++cnt,mid=(l+r)>>1;
        t[rt].val=a[mid];
        t[rt].ls=build(l,mid-1);
        t[rt].rs=build(mid+1,r);
        return rt;
    }
    il void update(int id,int pre,int pos,int k){
        ri int l=1,r=n,rt=rot[id]=++cnt,mid;
        while(pre){
            t[rt]=t[pre],mid=(l+r)>>1;
            if(mid==pos) {t[rt].val=k; break;}
            if(pos<mid) r=mid-1,t[rt].ls=++cnt,pre=t[pre].ls,rt=t[rt].ls;
            else l=mid+1,t[rt].rs=++cnt,pre=t[pre].rs,rt=t[rt].rs;
        }
        return;
    }
    il int ask(int rt,int pos){
        ri int l=1,r=n,mid;
        while(rt&&l<=r){
            mid=(l+r)>>1;
            if(mid==pos) return t[rt].val;
            if(pos<mid) r=mid-1,rt=t[rt].ls;
            else l=mid+1,rt=t[rt].rs;
        }
        return 0;
    }
}fa,sz;

namespace Set{
    il int up(int x,int i){
        ri int k;
        while((k=fa.ask(fa.rot[i],x))^x) x=k;
        return x;
    }
    il void merge(int a,int b,int i){
        a=up(a,i),b=up(b,i);
        if(a^b){
            ri int sza=sz.ask(sz.rot[i],a);
            ri int szb=sz.ask(sz.rot[i],b);
            if(sza>szb) swap(sza,szb),swap(a,b);
            fa.update(i,fa.rot[i],a,b);
            sz.update(i,sz.rot[i],b,sza+szb);
        }
        return;
    }
} using namespace Set;

signed main(){
    n=rd(),m=rd();
    for(ri int i=1;i<=n;++i) fa.a[i]=i,sz.a[i]=1;
    fa.rot[0]=fa.build(1,n),sz.rot[0]=sz.build(1,n);
    for(ri int i=1,op,a,b;i<=m;++i){
        op=rd(),fa.rot[i]=fa.rot[i-1],sz.rot[i]=sz.rot[i-1];
        if(op==1) a=rd(),b=rd(),merge(a,b,i);
        else if(op==2) a=rd(),fa.rot[i]=fa.rot[a],sz.rot[i]=sz.rot[a];
        else a=rd(),b=rd(),putchar((up(a,i)==up(b,i))|48),putchar(10);
    }
    return 0;
}

edit