[BZOJ3673&3674]可持久化并查集&加强版

题目大意:让你实现一个可持久化的并查集(3674强制在线)。

解题思路:刚刚介绍了一个叫rope的神器:我是刘邦,在这两题(实际上两题没什么区别)就派上用场了。

正解应该是主席树||可持久化平衡树,然而rope就是可持久化平衡树呵!

只需将rope当做数组般使用,并查集即可。

BZOJ3673 C++ Code:

#include<cstdio>
#include<ext/rope>
typedef __gnu_cxx::rope<int> rp;
rp *f[20005];
int n,m,i;
int a[20005];
int dad(int x){
	int p;
	if((p=f[i]->at(x))==x)return x;
	f[i]->replace(x,dad(p));
	return f[i]->at(x);
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i)a[i]=i;
	f[0]=new rp(a,a+n+1);
	for(i=1;i<=m;++i){
		f[i]=new rp(*f[i-1]);
		int op;
		scanf("%d",&op);
		if(op==1){
			int u,v;
			scanf("%d%d",&u,&v);
			u=dad(u),v=dad(v);
			if(u!=v)f[i]->replace(v,u);
		}else
		if(op==2){
			int t;
			scanf("%d",&t);
			f[i]=new rp(*f[t]);
		}else{
			int u,v;
			scanf("%d%d",&u,&v);
			printf("%d
",dad(u)==dad(v)?1:0);
		}
	}
	return 0;
}

 

而对于3674,唯一的问题就是路径压缩时,如果结果与当前值相等,就不需要更改值了,否则会炸内存MLE!

BZOJ3674 C++ Code:

 

#include<cstdio>
#include<ext/rope>
typedef __gnu_cxx::rope<int> rp;
rp *f[200005];
int n,m,i,lst;
int a[200005];
int dad(int x){
	int p;
	if((p=f[i]->at(x))==x)return x;
	p=dad(p);
	if(f[i]->at(x)==p)return p;
	f[i]->replace(x,p);
	return f[i]->at(x);
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i)a[i]=i;
	f[0]=new rp(a,a+n+1);
	for(i=1;i<=m;++i){
		f[i]=new rp(*f[i-1]);
		int op;
		scanf("%d",&op);
		if(op==1){
			int u,v;
			scanf("%d%d",&u,&v);
			u=dad(u^lst),v=dad(v^lst);
			if(u!=v)f[i]->replace(v,u);
		}else
		if(op==2){
			int t;
			scanf("%d",&t);
			f[i]=new rp(*f[t^lst]);
		}else{
			int u,v;
			scanf("%d%d",&u,&v);
			u^=lst;v^=lst;
			printf("%d
",lst=dad(u)==dad(v)?1:0);
		}
	}
	return 0;
}
原文地址:https://www.cnblogs.com/Mrsrz/p/7171096.html