[BZOJ3674]可持久化并查集

BZOJ强制在线
BZOJ不强制在线
luogu
博主以为自己学会主席树之后来看这题整个人都是木的(学艺不精)
现在终于敢来写一写了
考虑并查集按大小合并
为了实现可持久化
主席树维护sz和fa就行
版本与版本之间的处理需要注意一下
下面放的是强制在线的code

#include<bits/stdc++.h>
using namespace std;
const int _=2e5+5;
int re(){
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int n,m,now,top,ans;
int a[_],ver[_];
struct tr{
    int tot,rt[_],val[_*22],ls[_*22],rs[_*22];
    void bu(int&x,int l,int r){
        x=++tot;if(l==r){val[x]=a[l];return;}
        int mid=(l+r)>>1;bu(ls[x],l,mid);bu(rs[x],mid+1,r);
    }
    void upd(int&x,int l,int r,int k,int v){
        ++tot;ls[tot]=ls[x];rs[tot]=rs[x];x=tot;
        if(l==r){val[x]=v;return;}int mid=(l+r)>>1;
        k<=mid?upd(ls[x],l,mid,k,v):upd(rs[x],mid+1,r,k,v);
    }
    int q(int x,int l,int r,int k){
        if(l==r)return val[x];int mid=(l+r)>>1;
        return k<=mid?q(ls[x],l,mid,k):q(rs[x],mid+1,r,k);
    }
}fa,sz;
int find(int x){
    int f=fa.q(fa.rt[now],1,n,x);
    return x==f?x:find(f);
}
void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    int A=sz.q(sz.rt[now],1,n,x),B=sz.q(sz.rt[now],1,n,y);
    if(A<B)swap(x,y);++top;
    fa.rt[top]=fa.rt[now];
    fa.upd(fa.rt[top],1,n,y,x);
    sz.rt[top]=sz.rt[now];
    sz.upd(sz.rt[top],1,n,x,A+B);
    now=top;
}
int main(){
    n=re(),m=re();
    for(int i=1;i<=n;i++)a[i]=i;
    fa.bu(fa.rt[0],1,n);
    for(int i=1;i<=n;i++)a[i]=1;
    sz.bu(sz.rt[0],1,n);
    int op,a,b;
    for(int i=1;i<=m;i++){
        op=re(),a=re()^ans;
        if(op==1){b=re()^ans;unite(a,b);}
        if(op==2)now=ver[a];
        if(op==3){b=re()^ans;printf("%d\n",ans=(find(a)==find(b)));}
        ver[i]=now;
    }
    return 0;
}

[BZOJ3674]可持久化并查集

原文：https://www.cnblogs.com/sdzwyq/p/9909086.html