可持久化并查集学习笔记 | 题解P3402 可持久化并查集

简要题意

你需要维护一个并查集，支持版本回退，查连通性，合并两个点。

特别的，没进行一次操作都要新建一个版本。

前置知识

可持久化数组，如果您不会，出门左转【模板】可持久化线段树 1（可持久化数组）。
并查集

找根（find）

现在我们来考虑如何find。

首先我们来研究以下正常的并查集是怎么写的（不加任何优化）:

int find(int x){

	if(fa[x]==x){

		return x;

	}

	else{

		return find(fa[x]);

	}

}

事实上，我们只需要将 fa 替换成用可持久化数组维护，那么就可以实现可持久化了。（显然）

合并（merge）

同上，我们研究一下正常的并查集是怎么写的（同样，不加任何优化）：

void merge(int x,int y){

	fa[find(x)]=find(y); // 将 x 合并到 y 上。

}

大家可能回想，那我也吧 fa 改成可持久化的不就行了吗？

如果这样子……

合并的优化

如果直接暴力合并，那么会TLE。因为链就可以将你的 find 轻松卡到 \(O(n\log n)\)。

回忆一下并查集的优化，有下面这几种方式:

路径压缩
按秩合并

首先，不能路径压缩，因为路径压缩时间复杂度是均摊的，可以被人卡到 \(O(n\log n)\)。（同样，基于均摊复杂度的珂朵莉树、Splay 都不能简单的可持久化）

其次我们考虑按秩合并，其中的“秩”有下面几种：

随机，等到合并时修改，小的合并到大的。
按子树大小，小的合并到大的。
按子树最大深度（就是子树树高），小的合并到大的。

随机方案貌似被人Hack了。我们就用第二个吧（因为第三个不会写）。

那么我们又要开一个可持久化数组（建议用结构体封装），维护子树大小，记得合并后我们更新一下（就是将新的根的子树大小加上旧的根的子树大小）。

对于证明过程，@chenxinyang2006 的题解已经写的很清楚了，我就不赘述了。

实现操作与时间复杂度分析

合并就用上面介绍的。
查连通性我们就找两个节点的根，看它们是不是一样的。
回退版本我们就复制一个到当前版本即可。

时间复杂度，可持久化数组读写复杂度都是 \(O(\log n)\)，那么：

回退版本时间复杂度是 \(O(1)\) 的（因为只要普通数组赋值）。
找根的时间复杂度本身是 \(O(\log n)\) （优化了），乘上可持久化的时间复杂度就是 \(O(\log^{2}n)\)。
所以，查连通性时间复杂度是 \(O(\log^{2} n)\)。
合并的时间复杂度也是 \(O(\log^{2}n)\)（瓶颈在找根）。

整体时间复杂度为 \(O(n+m\log^{2}n)\)。可以通过本题。

代码

本代码封装了可持久化数组和并查集，供大家参考。

#include<bits/stdc++.h>

using namespace std;

int n,m;

namespace PersistentUnionFind{

	struct PersistentArray {

#define mid ((l+r)>>1)

		const static int SIZE = 1e5 + 5;

		struct {

			int l, r, v;

		} t[SIZE * 25];

		int top;

		int root[SIZE * 25];

		int a[SIZE];

		int newnode(int i) {

			t[++top] = t[i];

			return top;

		}

		int build(int i, int l, int r) {

			i = (++top);

			if (l == r) {

				t[i].v = a[l];

				return i;

			}

			t[i].l = build(t[i].l, l, mid);

			t[i].r = build(t[i].r, mid + 1, r);

			return i;

		}

		int update(int i, int l, int r, int p, int val) {

			i = newnode(i);

			if (l == r) {

				t[i].v = val;

				return i;

			}

			if (p <= mid) {

				t[i].l = update(t[i].l, l, mid, p, val);

			} else {

				t[i].r = update(t[i].r, mid + 1, r, p, val);

			}

			return i;

		}

		int query(int i, int l, int r, int p) {

			if (l == r) {

				return t[i].v;

			}

			if (p <= mid) {

				return query(t[i].l, l, mid, p);

			} else {

				return query(t[i].r, mid + 1, r, p);

			}

		}

		inline int Assign(int i, int version, int p, int val) {

			return update(root[version], 1, n, p, val);

		}

		inline int Get(int i, int version, int p) {

			return query(root[version], 1, n, p);

		}

		void copyVersion(int new_,const int dst){

			root[new_]=root[dst];

		}

		void newVersionFromPoint(int pos,int val){

			root[pos]=val;

		}

	} fa,siz;

	int find(int x,int version){

	    if(fa.Get(114514,version,x)==x){

	        return x;

	    }

		else{

		    return find(fa.Get(1919810,version,x),version);

		}

	}

	void merge(int x,int y,int version){

		int fx=find(x,version),fy=find(y,version);

		if(fx==fy)return;

		int xsiz=siz.Get(114514,version,fx),ysiz=siz.Get(1919810,version,fy);

		if(xsiz<=ysiz){

			fa.newVersionFromPoint(version,fa.Assign(114514,version,fx,fy));

			siz.newVersionFromPoint(version,siz.Assign(114514,version,fy,xsiz+ysiz));

		}

		else{

			fa.newVersionFromPoint(version,fa.Assign(114514,version,fy,fx));

			siz.newVersionFromPoint(version,siz.Assign(114514,version,fx,xsiz+ysiz));

		}

	}

	bool same(int x,int y,int version){

		return find(x,version)==find(y,version);

	}

}

signed main(){

	cin>>n>>m;

	for(int i=1;i<=n;i++){

		PersistentUnionFind::fa.a[i]=i;

		PersistentUnionFind::siz.a[i]=1;

	}

	PersistentUnionFind::fa.newVersionFromPoint(0,PersistentUnionFind::fa.build(1,1,n));

	PersistentUnionFind::siz.newVersionFromPoint(0,PersistentUnionFind::siz.build(1,1,n));

	for(int i=1;i<=m;i++){

		int op,x,y;

		cin>>op>>x;

		PersistentUnionFind::fa.copyVersion(i,i-1);

		PersistentUnionFind::siz.copyVersion(i,i-1);

		if(op==1){

			cin>>y;

			PersistentUnionFind::merge(x,y,i);

		}

		if(op==2){

			PersistentUnionFind::fa.copyVersion(i,x);

			PersistentUnionFind::siz.copyVersion(i,x);

		}

		if(op==3){

			cin>>y;

			cout<<PersistentUnionFind::same(x,y,i)<<'\n';

		}

	}

	return 0;

}

AC Record

巴特西