首页 > 代码库 > 【bzoj3674】 可持久化并查集加强版

【bzoj3674】 可持久化并查集加强版

http://www.lydsy.com/JudgeOnline/problem.php?id=3674 (题目链接)

题意

  维护并查集3个操作:合并;回到完成第k个操作后的状态;查询。

Solution

  其实就是用主席树的叶子节点维护并查集的可持久化数组fa[]。

细节

  终于认识到了按秩合并的强大,单纯写个路径压缩Re飞,写了路径压缩+按秩合并比单纯的按秩合并每快多少→_→

代码

// bzoj3674#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=200010,maxm=10000010;struct tree {int ls,rs;}tr[maxm];int fa[maxm],deep[maxm],rt[maxn],n,m,sz;void build(int &k,int l,int r) {	if (!k) k=++sz;	if (l==r) {fa[k]=l;return;}	int mid=(l+r)>>1;	build(tr[k].ls,l,mid);	build(tr[k].rs,mid+1,r);}void update(int &k1,int k2,int l,int r,int x,int val) {	k1=++sz;tr[k1]=tr[k2];	int mid=(l+r)>>1;	if (l==r) {fa[k1]=val,deep[k1]=deep[k2];return;}	if (x<=mid) update(tr[k1].ls,tr[k2].ls,l,mid,x,val);	else update(tr[k1].rs,tr[k2].rs,mid+1,r,x,val);}void add(int k,int l,int r,int x) {	if (l==r) {deep[k]++;return;}	int mid=(l+r)>>1;	if (x<=mid) add(tr[k].ls,l,mid,x);	else add(tr[k].rs,mid+1,r,x);}int query(int k,int l,int r,int x) {	int mid=(l+r)>>1;	if (l==r) return k;	if (x<=mid) return query(tr[k].ls,l,mid,x);	else return query(tr[k].rs,mid+1,r,x);}int find(int k,int x) {	int p=query(k,1,n,x);	if (x==fa[p]) return p;	int t=find(k,fa[p]);	update(k,k,1,n,fa[p],fa[t]);	return t;}int main() {	scanf("%d%d",&n,&m);	build(rt[0],1,n);	int ans=0;	for (int op,a,b,i=1;i<=m;i++) {		scanf("%d",&op);		if (op==1) {			rt[i]=rt[i-1];			scanf("%d%d",&a,&b);a^=ans,b^=ans;			int r1=find(rt[i],a),r2=find(rt[i],b);			if (fa[r1]==fa[r2]) continue;			//if (deep[r1]>deep[r2]) swap(r1,r2);			update(rt[i],rt[i-1],1,n,fa[r1],fa[r2]);			//if (deep[r1]==deep[r2]) add(rt[i],1,n,fa[r2]);		}		if (op==2) {scanf("%d",&a);a^=ans;rt[i]=rt[a];}		if (op==3) {			rt[i]=rt[i-1];			scanf("%d%d",&a,&b);			a^=ans,b^=ans;			int r1=find(rt[i],a),r2=find(rt[i],b);			ans=fa[r1]==fa[r2] ? 1 : 0;			printf("%d\n",ans);		}	}	return 0;}

  

【bzoj3674】 可持久化并查集加强版