欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P3402 可持久化并查集

程序员文章站 2024-03-02 21:59:22
...

P3402 可持久化并查集

题意:

给定 n 个集合,第 i 个集合内初始状态下只有一个数,为 i。

有 m 次操作。操作分为 3 种:

1 a b 合并a,b 所在集合;

2 k 回到第 k 次操作(执行三种操作中的任意一种都记为一次操作)之后的状态;

3 a b 询问 a,b 是否属于同一集合,如果是则输出 1,否则输出 0。

题解:

可持久化并查集模板题
这个博客讲的非常详细
按sz合并一般称为启发式合并,按height合并一般称为按秩合并,代码中是按秩合并

按秩合并其实就是,我们以树高为秩,每次将树高低的树合并到树高高的树上,那么对于树高高的树来说树高并没有变(也就说原树访问根节点的代价并没有变),而树高低的树访问根节点的代价只增加了1(这棵树的根节点变成了树高高的树的儿子)。
还有一种特殊情况那就是两棵树树高相同。这个时候把树A合并到树B上,B的树高会增加1,而树A的高度则不会改变。

代码:

#include<bits/stdc++.h>
#define N 301000
using namespace std;
int n,m;
int L[N*30],R[N*30],fa[N*30],dep[N*30];
int root[N*30];

int cnt;
void build(int &rt,int l,int r)
{
    rt=++cnt;
    if(l==r){
		fa[rt]=l;
		return ;
	}
    build(L[rt],l,((l+r)>>1));
	build(R[rt],((l+r)>>1)+1,r);
}
void merge(int last,int &rt,int l,int r,int pos,int Fa)
{
    rt=++cnt;
	L[rt]=L[last];
	R[rt]=R[last];
    if(l==r)
    {
        fa[rt]=Fa;
        dep[rt]=dep[last];
        return ;
    }
    if(pos<=((l+r)>>1))merge(L[last],L[rt],l,((l+r)>>1),pos,Fa);
    else merge(R[last],R[rt],((l+r)>>1)+1,r,pos,Fa);
}
void update(int rt,int l,int r,int pos)
{
    if(l==r){
		dep[rt]++;
		return ;
	}
    if(pos<=((l+r)>>1))update(L[rt],l,((l+r)>>1),pos);
    else update(R[rt],((l+r)>>1)+1,r,pos);
}
int query(int rt,int l,int r,int pos)
{
    if(l==r)return rt;
    if(pos<=((l+r)>>1))return query(L[rt],l,((l+r)>>1),pos);
    else return query(R[rt],((l+r)>>1)+1,r,pos);
}
int find(int rt,int pos)
{
    int now=query(rt,1,n,pos);
    if(fa[now]==pos)return now;
    return find(rt,fa[now]);
}
int main()
{
    cin>>n>>m;
    build(root[0],1,n);
    for(int i=1;i<=m;i++)
    {
        static int opt,x,y;
        cin>>opt>>x;
        if(opt==1)
        {
            cin>>y;
            static int posx,posy;
            root[i]=root[i-1];
            posx=find(root[i],x);
			posy=find(root[i],y);
            if(fa[posx]!=fa[posy])
            {
            	// 按秩合并 
                if(dep[posx]>dep[posy])swap(posx,posy);//保证dep[posx]<dep[posy] 
                merge(root[i-1],root[i],1,n,fa[posx],fa[posy]);
                if(dep[posx]==dep[posy])update(root[i],1,n,fa[posy]);
            }
        }
        else if(opt==2)root[i]=root[x];
        else if(opt==3)
        {
            cin>>y;
            root[i]=root[i-1];
            static int posx,posy;
            posx=find(root[i],x);
			posy=find(root[i],y);
            if(fa[posx]==fa[posy])puts("1");
            else puts("0");
        }
    }
    return 0;
}