【学习笔记】可持久化并查集（BZOJ3673）

好久之前就想学了然后今天恰巧一道题需要用到就学了

前置芝士

1.主席树[可持久化数组]

2.并查集

如果你掌握了前面两个那么这个东西你就会觉得非常沙茶。。

构造

可持久化并查集 = 主席树 + 并查集

有点蠢= =

当然我们这里的并查集是要按秩合并的并查集

[按秩合并：就是把dep小的连接到大的上面这个复杂度分析出来是O(lgn)的原因不要问我我不知道= =]

不可以路径压缩原因好像是可以被极限数据卡掉？[我也不知道路径压缩了你怎么访问历史版本的emm。。]

这样的话我们每次开log个节点连下来然后对于每个点维护fa和dep就可以了

然后dep的更新就是当两个高度一样的时候连起来那么被连的深度需要+1

就没了qwq。

例题就是BZOJ3673 真·模板

代码。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define inf 20021225

#define ll long long

#define mxn 200010

#define pa pair<int,int>

#define mp make_pair

using namespace std;

struct node{int ls,rs,fa,dep;}t[mxn*40];

int cnt,rt[mxn],n;

void build(int &x,int l,int r)

{

	x=++cnt;

	if(l==r){t[x].fa=l;t[x].dep=1;return;}

	int mid=l+r>>1;

	build(t[x].ls,l,mid); build(t[x].rs,mid+1,r);

}

void insert(int &x,int lt,int l,int r,int d,int fa)

{

	x=++cnt; t[x] = t[lt];

	if(l==r){t[x].fa = fa; return;}

	int mid = l+r>>1;

	if(d<=mid) insert(t[x].ls,t[lt].ls,l,mid,d,fa);

	else	insert(t[x].rs,t[lt].rs,mid+1,r,d,fa);

}

void update(int x,int l,int r,int d)

{

	if(l==r){t[x].dep++; return;}

	int mid = l+r>>1;

	if(d<=mid)	update(t[x].ls,l,mid,d);

	else	update(t[x].rs,mid+1,r,d);

}

int query(int x,int l,int r,int d)

{

	if(l==r)	return x;

	int mid = l+r>>1;

	if(d<=mid)	return query(t[x].ls,l,mid,d);

	else	return query(t[x].rs,mid+1,r,d);

}

int find(int root,int x)

{

	int pos = query(root,1,n,x);

	if(t[pos].fa==x)	return pos;

	return find(root,t[pos].fa);

}

int main()

{

	int m,opt,x,y;

	scanf("%d%d",&n,&m);

	build(rt[0],1,n);

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

	{

		scanf("%d%d",&opt,&x);

		if(opt==2){rt[i]=rt[x];continue;}

		scanf("%d",&y); rt[i]=rt[i-1];

		int fx = find(rt[i],x),fy = find(rt[i],y);

		if(opt==1)

		{

			if(fx!=fy)

			{

				if(t[fx].dep < t[fy].dep)	swap(fx,fy);

				int ffx = t[fx].fa , ffy = t[fy].fa;

				insert(rt[i],rt[i-1],1,n,ffy,ffx);

				if(t[fx].dep == t[fy].dep)	update(rt[i],1,n,ffx);

			}

		}

		else	printf("%d\n",t[fx].fa==t[fy].fa);

	}

	return 0;

}

巴特西

【学习笔记】可持久化并查集（BZOJ3673）

最新文章

热门文章