可持久化并查集

可持久化并查集

简单来说就是两颗主席树
一颗维护 父亲节点是谁
一颗维护 深度

为什么要维护深度？

降低时间复杂度
并查集如果不优化的查询的话是这样:

int findx(int x)
{
   
	return x == fa[x]?x : findx(fa[x]);
}
void hebing(int x,int y)
{
   
	int xx = findx(x);
	int yy = findx(y);
	if(xx != yy)
	{
   
		fa[xx] = yy;
	}
}

这个时间复杂度最坏可以到达O(n) 的
优化一：
路径压缩是这样：
基本是常数复杂度?

void hebing(int x,int y)
{
   
	int xx = findx(x);
	int yy = findx(y);
	if(xx != yy)
	{
   
		fa[xx] = yy;
	}
}
int findx(int x)
{
   
	return x == fa[x]?x : fa[x] = findx(fa[x]);
}

但是可持久化的话这样每压缩一次就算一个状态？ 可能会MLE？
优化二:
按秩合并：
就是按照他的这个树的大小来合并，把小的树的根节点连到大的树的根节点上面这样可以使树尽量低 查询的复杂度是logn
代码是这样：

int findx(int x)
{
   
	return x == fa[x]?x :findx(fa[x]);
}
void hebing(int x,int y)
{
   
	int xx = findx(x);
	int yy = findx(y);
	if(xx != yy)
	{
   
		int dx = dep[xx];
		int dy = dep[yy];
		if(dx<dy)//此时树的深度不变 
		{
   
			fa[xx] = yy;
		}
		else if(dx> dy)//此时深度也不便
		{
   
			fa[yy] = xx;
		}
		else
		{
   
			fa[xx] = yy;
			dep[yy]++;//深度加了1
		}
	}
}

一般写的话应该都写的是那个路径压缩的那个 因为合并查询都很简单而且复杂度还低 但是可持久化的时候可能爆内存。
还有一些别的优化的方法。但是我太菜了不知道

然后可持久化并查集就采用按秩合并

分析一下过程：
查询一个结点的父节点 : 因为在主席树里 所以是 log(n)
查询一个结点的根节点：log(n)*log(n);
合并：查询两个节点当前状态的的根节点，然后查询根节点当前状态的深度，然后按秩合并就好了

可持久化的话只用把fa数组和深度dep数组可持久化就好了 所以是两颗主席树。

两颗主席树都存的是：左节点、右节点、值。
所以用一个结构体，内存开二倍就好了。
两个根数组，一个父亲一个深度
用不用建树？初始化的时候 i 的父节点是 i ，深度都是0；
所以只用建父节点就行了

具体看代码

板子题: 洛谷 P 3402
然后代码:

#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 2e5+5;
struct Node
{
   
    int l,r,num;
}node[maxn*40*2];
int rfa[maxn];
int rdep[maxn];
int cnt;//
int stemp;
//stemp有什么用？ 建树的时候记录
void build(int l,int r,int& no)
{
   
    no = ++cnt;
    if(l == r)
    {
   
        node[no].num = ++stemp;
// printf("%d\n",node[no].num);
        return;
    }
    int mid = l + r >> 1;
    build(l,mid,node[no].l);
    build(mid+1,r,node[no].r);
}

void update(int l,int r,int per,int &no,int pos,int num)
{
   
    no = ++cnt;
    node[no] = node[per];
    if(l == r)
    {
   
        node[no].num = num;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(l,mid,node[per].l,node[no].l,pos,num);
    else update(mid+1,r,node[per].r,node[no].r,pos,num);
}

int query(int l,int r,int no,int pos)
{
   
// printf("%d %d\n",no,pos);
    if(l == r)
        return node[no].num;
    int mid = l + r >> 1;
    if(pos <= mid) return query(l,mid,node[no].l,pos);
    else return query(mid+1,r,node[no].r,pos);
}
int n;
int find(int x,int i)
{
   
// printf("%d %d\n",x,i);
    int xx = query(1,n,rfa[i],x);
    if(xx == x) return x;
    else return find(xx,i);
}

int main()
{
   
    int m;
    scanf("%d%d",&n,&m);
    build(1,n,rfa[0]);
// rfa[0] = 1;
    for (int i = 1; i <= m; i ++ )
    {
   
        int f,x,y;
        scanf("%d",&f);
        if(f == 1)
        {
   
            scanf("%d%d",&x,&y);
            int fx = find(x,i-1);
            int fy = find(y,i-1);
            if(fx == fy)
            {
   
                rdep[i] = rdep[i-1];
                rfa[i] = rfa[i-1];
                continue;
            }
            x = fx;
            y = fy;
            int dex = query(1,n,rdep[i-1],x);
            int dey = query(1,n,rdep[i-1],y);
            if(dex < dey)
            {
   
                update(1,n,rfa[i-1],rfa[i],x,y);
                rdep[i] = rdep[i-1];
            }
            else if(dex > dey)
            {
   
                update(1,n,rfa[i-1],rfa[i],y,x);
                rdep[i] = rdep[i-1];
            }
            else
            {
   
                update(1,n,rfa[i-1],rfa[i],x,y);
                update(1,n,rdep[i-1],rdep[i],y,dey+1);
            }
        }
        else if(f == 2)
        {
   
            scanf("%d",&x);
            rfa[i] = rfa[x];
            rdep[i] = rdep[x];
        }
        else
        {
   
            scanf("%d%d",&x,&y);
// printf("111111\n");
            int fax = find(x,i-1);
            int fay = find(y,i-1);
            if(fax == fay)
                printf("1\n");
            else
                printf("0\n");
            rfa[i] = rfa[i-1];
            rdep[i] = rdep[i-1];
        }
// printf("%d %d f\n",i,f);
    }
}

看b站习得 大佬链接