这两天做了两道“启发式合并”的题，似乎“启发式合并”就是每次把节点数小的依次放到节点数大的地方，对只有合并操作的题能做到logn的时间复杂度

[BZOJ1483][HNOI2009]梦幻布丁：链表的启发式合并

每次把短的安到长的上面再判断

#include<cstdio>
#define N 1111111
using namespace std;
int n,m,i,ii,p,ans,x,y,t,tmp,a[N],now[N],first[N],next[N],color[N],ft[N];
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		color[a[i]]++;
		ft[a[i]]=a[i];
		if(a[i]!=a[i-1])ans++;
		if(!first[a[i]])first[a[i]]=i;
		next[now[a[i]]]=i;
		now[a[i]]=i;
	}
	for(ii=1;ii<=m;ii++){
		scanf("%d",&p);
		if(p==2)printf("%d\n",ans);else{
			scanf("%d%d",&x,&y);
			if(x==y)continue;
			if(color[ft[x]]>color[ft[y]])t=ft[x],ft[x]=ft[y],ft[y]=t;
			x=ft[x];y=ft[y];
			if(color[x]==0)continue;
			for(i=first[x];i;i=next[i]){
				tmp=i;
				if(a[i+1]==y)ans--;
				if(a[i-1]==y)ans--;
			}
			for(i=first[x];i;i=next[i])a[i]=y;
			next[tmp]=first[y];first[y]=first[x];
			color[y]+=color[x];first[x]=color[x]=0;
		}
	}
}

[BZOJ2733][HNOI2012]永无乡：Splay的启发式合并

每次把小的Splay暴力拆掉，加入到大的Splay上面，第一次写无根Splay、、

#include<cstdio>
#include<iostream>
#define N 111111
using namespace std;
int n,m,T,x,y,p,q,k,i,top,father[N],son[N][2],size[N],val[N],num[N],zhi[N];char s[9];
int find(int x){while(father[x])x=father[x];return x;}
void pushup(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;}
void newnode(int x,int fa,int da){father[x]=fa;size[x]=1;val[x]=da;son[x][0]=son[x][1]=0;}
void rotate(int x,int k){
	int y=father[x];
	son[y][!k]=son[x][k];father[son[y][!k]]=y;
	son[father[y]][son[father[y]][1]==y]=x;
	father[x]=father[y];
	son[x][k]=y;father[y]=x;
	pushup(y);
}
void splay(int x){
	while(father[x]){
		int y=father[x],z=father[y],f=(son[z][0]==y);
		if(!z)rotate(x,son[y][0]==x);else{
			if(son[y][f]==x)rotate(x,!f);else rotate(y,f);
			rotate(x,f);
		}
	}
	pushup(x);
}
void insert(int x,int number,int key){
	while(son[x][key>val[x]])size[x]++,x=son[x][key>val[x]];
	size[x]++;son[x][key>val[x]]=number;
	newnode(number,x,key);
	splay(number);
}
void intour(int x){
	if(!x)return;num[++top]=x;zhi[top]=val[x];
	intour(son[x][0]);intour(son[x][1]);
}
int find(int x,int k){
	if(size[son[x][0]]+1==k)return x;
	if(size[son[x][0]]>=k)return find(son[x][0],k);
	return find(son[x][1],k-size[son[x][0]]-1);
}
void link(){
	scanf("%d%d",&x,&y);p=find(x);q=find(y);
	if(p!=q){
		if(size[p]>size[q])swap(p,q),swap(x,y);
		top=0;intour(p);
		for(int i=1;i<=top;i++)insert(q,num[i],zhi[i]);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&val[i]),size[i]=1;
	for(i=1;i<=m;i++)link();
	scanf("%d",&T);
	while(T--){
		scanf("%s",s);
		if(s[0]=='B')link();else{
			scanf("%d%d",&x,&k);
			splay(x);
			if(k>size[x])puts("-1");else printf("%d\n",find(x,k));
		}
	}
}

似乎启发式合并都是HNOI的，看来ZJOI是不会考这么简单的题目的、、

• 相关文章推荐
• 全局相关文章