数据结构 可持久化并查集

最近开始研究“可持久化”，顺便练一练

普通并查集

事实上，总结一下普通并查集，无非就是利用fa[]数组来记录节点间的联系。

可持久化并查集

将并查集可持久化，本质上就是可持久化一个数组。而可持久化数组正是万恶之源——主席树。通过主席树来可持久化fa[]数组即可

但是在尝试路径压缩的时候出了点问题。众所周知，主席树每一次只增加一条链，也就是说只能对原数组进行一次更改。而路径压缩就可能导致一条路径上很多点都被更改，需要大量新建链，丧失了主席树的灵魂

因此，我们改而采用“按秩合并”

按秩合并的思路很简单，将深度小的子树接到深度大的子树上。这么做可以保证只修改一个点的同时，将复杂度优化到\(O(\log n)\)

具体而言

合并时保证dep_a\(\geq\)dep_b

将fa[b]改为fa_a

倘若dep_a=dep_b,那么dep[fa_a]++

就是酱紫，例题好像只有作为暴力解法的[NOI2018]归程

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXD=1e8+5,MAXN=4e5+5;

struct data{
    int lson,rson,val;
}node[MAXD];

int n,m,tot;
int root_fa[MAXN],root_dep[MAXN];

inline int read();
void build_fa(int,int,int);
void build_dep(int,int,int);
void create(int);
void copy(int,int);
void modify(int,int,int,int,int,int);
int query(int,int,int,int);
int find(int,int);
bool check(int,int,int);

void debug(int);

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    n=read(); m=read();

    root_fa[0]=++tot; build_fa(root_fa[0],1,n);
    root_dep[0]=++tot; build_dep(root_dep[0],1,n);

    for(int i=1;i<=m;++i){
        int type,a,b,k; type=read();
        int fa_a,fa_b,dep_a,dep_b;
        create(i);
        switch(type){
            case 1:
            a=read(); b=read();
            fa_a=find(a,i-1); fa_b=find(b,i-1);
            if(fa_a==fa_b) {copy(i-1,i); break;}
            dep_a=query(root_dep[i-1],1,n,fa_a);
            dep_b=query(root_dep[i-1],1,n,fa_b);
            if(dep_a<dep_b) {swap(a,b); swap(fa_a,fa_b); swap(dep_a,dep_b);}
            modify(root_fa[i-1],root_fa[i],1,n,fa_b,fa_a);
            if(dep_a==dep_b) modify(root_dep[i-1],root_dep[i],1,n,fa_a,dep_a+1);
            else modify(root_dep[i-1],root_dep[i],1,n,fa_a,dep_a);
            break;

            case 2:
            k=read();
            copy(k,i);
            break;

            case 3:
            copy(i-1,i);
            a=read(); b=read();
            printf("%d\n",check(a,b,i));
            break;
        }
    }

    return 0;
}

inline int read(){
    char tmp=getchar(); int sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;
}

void build_fa(int p,int l,int r){
    if(l==r) {node[p].val=l; return;}
    int mid=(l+r)>>1;
    node[p].lson=++tot; build_fa(node[p].lson,l,mid);
    node[p].rson=++tot; build_fa(node[p].rson,mid+1,r);
}

void build_dep(int p,int l,int r){
    if(l==r) {node[p].val=1; return;}
    int mid=(l+r)>>1;
    node[p].lson=++tot; build_dep(node[p].lson,l,mid);
    node[p].rson=++tot; build_dep(node[p].rson,mid+1,r);
}

void create(int k){
    root_fa[k]=++tot; root_dep[k]=++tot;
}

void copy(int a,int b){
    int ra=root_fa[a]; int rb=root_fa[b];
    node[rb].lson=node[ra].lson;
    node[rb].rson=node[ra].rson;
    ra=root_dep[a]; rb=root_dep[b];
    node[rb].lson=node[ra].lson;
    node[rb].rson=node[ra].rson;
}

void modify(int pre,int p,int l,int r,int pos,int k){
    node[p].lson=node[pre].lson;
    node[p].rson=node[pre].rson;

    if(l==r) {node[p].val=k; return;}

    int mid=(l+r)>>1;
    if(pos<=mid) {node[p].lson=++tot; modify(node[pre].lson,node[p].lson,l,mid,pos,k);}
    if(mid+1<=pos) {node[p].rson=++tot; modify(node[pre].rson,node[p].rson,mid+1,r,pos,k);}
}

int query(int p,int l,int r,int k){
    if(l==r) return node[p].val;
    int mid=(l+r)>>1;
    if(k<=mid) return query(node[p].lson,l,mid,k);
    if(mid+1<=k) return query(node[p].rson,mid+1,r,k);
}

int find(int u,int ver){
    int v=query(root_fa[ver],1,n,u);
    while(u!=v) {u=v; v=query(root_fa[ver],1,n,u);}
    return v;
}

bool check(int a,int b,int ver){
    return find(a,ver)==find(b,ver);
}

void debug(int ver){
    cout<<"This is version No."<<ver<<endl;
    for(int i=1;i<=n;++i){
        int fa=find(i,ver);
        cout<<fa<<" "<<query(root_dep[ver],1,n,fa)<<endl;
    }
    cout<<endl;
}