BZOJ3674/3673: 可持久化并查集加强版

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3674

Solution

双倍经验好评。
并查集按秩合并，因为每次只会改一个点，所以把每个点的fa和deep用主席树维护。
一遍过啦啦啦~

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 200005
#define N 8000020
#define ll int
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch>'9'||ch<'0'){if (ch=='-') f=-1; ch=getchar();}
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
inline void writeln(ll x){
    write(x); putchar('\n');
}
ll root[M],fa[N],left[N],right[N],deep[N];
ll n,m,a,b,u,v,size,opt,k;
void build(ll l,ll r,ll &p){
    if (!p) p=++size;
    if (l==r){fa[p]=l; return;}
    ll mid=l+r>>1;
    build(l,mid,left[p]); build(mid+1,r,right[p]);
}
void modify(ll l,ll r,ll x,ll &y,ll pos,ll v){
    y=++size;
    if (l==r){fa[y]=v; return;}
    left[y]=left[x]; right[y]=right[x];
    ll mid=l+r>>1;
    if (pos<=mid) modify(l,mid,left[x],left[y],pos,v);
    else modify(mid+1,r,right[x],right[y],pos,v);
}
void add(ll l,ll r,ll pos,ll p){
    if (l==r){deep[p]++; return;}
    ll mid=l+r>>1;
    if (pos<=mid) add(l,mid,pos,left[p]);
    else add(mid+1,r,pos,right[p]);
}
ll query(ll l,ll r,ll pos,ll p){
    if (l==r) return p;
    ll mid=l+r>>1;
    if (pos<=mid) return query(l,mid,pos,left[p]);
    else return query(mid+1,r,pos,right[p]);
}
ll find(ll p,ll x){
    ll k=query(1,n,x,p);
    if (fa[k]==x) return k;
    return find(p,fa[k]);
}
int main(){
    n=read(); m=read();
    build(1,n,root[0]);
    for (ll i=1;i<=m;i++){
        opt=read(); root[i]=root[i-1];
        if (opt==1){
            a=read(); b=read();
            u=find(root[i],a); v=find(root[i],b);
            if (fa[u]==fa[v]) continue;
            if (deep[u]>deep[v]) swap(u,v);
            modify(1,n,root[i-1],root[i],fa[u],fa[v]);
            add(1,n,fa[v],root[i]);
        }else
        if (opt==2){
            k=read(); root[i]=root[k];
        }else
        if (opt==3){
            root[i]=root[i-1];
            a=read(); b=read();
            u=find(root[i],a); v=find(root[i],b);
            writeln(fa[u]==fa[v]);
        }
    }
}