可持久化并查集学习笔记

唉据说这个玩意可以水过NOI2018归程，学一下美滋滋

板子题题面见https://www.luogu.org/problemnew/show/P3402

言归正传，这个也是历史版本修改查询，那么就上主席树了呗

维护三个操作

操作一：合并当前情况的a，b集合

操作二：回到某一个历史版本

操作三：查询当前版本的a，b是否在同一个集合

先剧透一下裸的并查集写法会TLE两个点，那么这样可持久化貌似不能路径压缩，那么就按秩合并优化（优化完跑得比香港记者都快）

那么如果让你在线段树记录并查集的信息，第一反应应该是记录一下自己的父亲在哪，然后记录一下自己的儿子秩是多少

然后仔细思考会发现合并的时候只要修改一个端点的父亲和另一个端点的秩罢了，修改可以压成log级的

查询也就是从当前版本的根向下走，查询也就是log而已

那么再加上之前主席树的写法，这道题就过了

（我在修改秩的时候写挂了，变成了裸的并查集，然后轻松TLE两个点，改了半天）

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<3)+(w<<1)+ch-48;
        ch=getchar();
    }
    return w*f;
}
int cnt,n,m,root[5000010],a[5000010],tot;
struct node{
    int ls,rs,dep,f;
}st[50000010];
inline int build(int l,int r){
    int pos=cnt++;
    if(l==r){
        st[pos].f=l;return pos;//到了叶子节点，初始化的是父亲是自己，与常规并查集一样 
    }
    int mid=(l+r)>>1;
    st[pos].ls=build(l,mid);
    st[pos].rs=build(mid+1,r);
    return pos;
}//建树写法完全与普通主席树一样啊 
inline int query(int p,int l,int r,int pos){//查询某版本的某节点 
    if(l==r) return p;//其实就是常规线段树查询方法啊 
    int mid=(l+r)>>1;
    if(pos<=mid) return query(st[p].ls,l,mid,pos);
    else return query(st[p].rs,mid+1,r,pos);
}
inline int find(int tim,int x){//大力找父亲 
    int now=query(tim,1,n,x); 
    if(st[now].f==x) return now;//父亲就是自身的话就到了端点了 
    else return find(tim,st[now].f);//没有的话就接着找啊 
}
inline int update(int tim,int l,int r,int p,int k){
    int pos=cnt++;
    if(l==r){//更新父节点 
        st[pos].f=k;st[pos].dep=st[tim].dep;return pos;//记得把原来节点上的秩搬过来啊，这很重要 
    }
    st[pos].ls=st[tim].ls;
    st[pos].rs=st[tim].rs;
    int mid=(l+r)>>1;
    if(p<=mid) st[pos].ls=update(st[tim].ls,l,mid,p,k);
    else st[pos].rs=update(st[tim].rs,mid+1,r,p,k);
    return pos;
}//常规主席树新建节点写法 
inline void add(int p,int l,int r,int pos){
    if(l==r){
        st[p].dep++;return;//修改端点的秩 
    }
    int mid=(l+r)>>1;
    if(pos<=mid) add(st[p].ls,l,mid,pos);
    else add(st[p].rs,mid+1,r,pos);
}
int main(){
    n=read();m=read();int i,j,k;
    root[0]=build(1,n);//先建树，记下第0个版本的根 
    for(i=1;i<=m;i++){//按照题目要求进行操作即可 
        int type=read();
        if(type==1){
            root[i]=root[i-1];
            int x=read();int y=read();
            int fx=find(root[i],x);
            int fy=find(root[i],y);
            if(st[fx].f==st[fy].f) continue;
            if(st[fx].dep>st[fy].dep) swap(fx,fy);
            root[i]=update(root[i-1],1,n,st[fx].f,st[fy].f);
            if(st[fx].dep==st[fy].dep) add(root[i],1,n,st[fy].f);
        }
        if(type==2){
            int x=read();root[i]=root[x];
        }
        if(type==3){
            root[i]=root[i-1];
            int x=read();int y=read();
            int fx=find(root[i],x);
            int fy=find(root[i],y);
            if(st[fx].f==st[fy].f) puts("1");
            else puts("0");
        }
    }
    return 0;
}

可持久化并查集学习笔记

相关推荐