「BZOJ3673」可持久化并查集 by zky

2014年8月1日25,13016

Description

n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

0<n,m<=2*10^4

Sample Input

5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

Sample Output

1
0
1

题解

这题不知道出题人什么做法，但是代码很短的样子

UPD：出题人用的是rope，即stl中的可持久化平衡树

KuribohG神犇告诉了我可以用可持久化线段树实现可持久化数组T T

既然都有可持久化数组了，只要用个再并查集的启发式合并就能妥妥的水过了（这样每次只要修改一个fa）

并查集的启发式合并就是按秩合并，初始所有集合秩为0

合并把秩小的树根的父亲设为秩大的树根

如果秩相同，则随便选取一个作为父节点并将它的秩+1

秩和fa一样维护

但是其实这题数据随机的话随便合并就行了，根本不用按秩合并什么的

UPD：秩其实有的时候很不好用，维护子树大小比较赞。。。

另外，ndsf发现只要直接暴力就能虐了T T

#include<cstdio>
#include<iostream>
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,sz;
int root[200005],ls[2000005],rs[2000005],v[2000005],deep[2000005];
void build(int &k,int l,int r)
{
	if(!k)k=++sz;
	if(l==r){v[k]=l;return;}
	int mid=(l+r)>>1;
	build(ls[k],l,mid);
	build(rs[k],mid+1,r);
}
void modify(int l,int r,int x,int &y,int pos,int val)
{
	y=++sz;
	if(l==r){v[y]=val;deep[y]=deep[x];return;}
	ls[y]=ls[x];rs[y]=rs[x];
	int mid=(l+r)>>1;
	if(pos<=mid)
		modify(l,mid,ls[x],ls[y],pos,val);
	else modify(mid+1,r,rs[x],rs[y],pos,val);
}
int query(int k,int l,int r,int pos)
{
	if(l==r)return k;
	int mid=(l+r)>>1;
	if(pos<=mid)return query(ls[k],l,mid,pos);
	else return query(rs[k],mid+1,r,pos);
}
void add(int k,int l,int r,int pos)
{
	if(l==r){deep[k]++;return;}
	int mid=(l+r)>>1;
	if(pos<=mid)add(ls[k],l,mid,pos);
	else add(rs[k],mid+1,r,pos);
}
int find(int k,int x)
{
    int p=query(k,1,n,x);
	if(x==v[p])return p;
    return find(k,v[p]);
}
int main()
{
	n=read();m=read();
	build(root[0],1,n);
	int f,k,a,b;
	for(int i=1;i<=m;i++)
	{
		f=read();
		if(f==1)
		{
			root[i]=root[i-1];
			a=read();b=read();
			int p=find(root[i],a),q=find(root[i],b);
			if(v[p]==v[q])continue;
			if(deep[p]>deep[q])swap(p,q);
			modify(1,n,root[i-1],root[i],v[p],v[q]);
			if(deep[p]==deep[q])add(root[i],1,n,v[q]);
		}
		if(f==2)
		{k=read();root[i]=root[k];}
		if(f==3)
		{
			root[i]=root[i-1];
			a=read();b=read();
		    int p=find(root[i],a),q=find(root[i],b);
			if(v[p]==v[q])puts("1");
			else puts("0");
		}
	}
	return 0;
}