要求维护一个数据结构，支持：

（1）一开始有n个集合，每个集合内一个元素

（2）合并两个集合

（3）询问一个集合内元素的最小值，并删除

裸的可并堆。

第一次尝试写斜堆。斜堆代码很短，时间复杂度也有保证。（均摊logn)。

这道题是小根堆。key[A]表示A堆的堆顶最小值。

int Merge(A,B):先保证key[A]<=key[B]。然后Merge(A的右子树，B)，递归进行。然后交换A的左右子树。最后返回A。

找根什么的用并查集维护。

删除堆顶元素的时候，只要Merge它的两个子树就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000010;
int rt[maxn],ls[maxn]={0},rs[maxn]={0},key[maxn],fa[maxn],d[maxn]={0};char op[2];
int getfa(int x){
	return x==fa[x] ? x : fa[x] = getfa(fa[x]);
}int merge(int a,int b){
	if(!a || !b)	return a+b;
	if(key[a] > key[b])	swap(a,b);
	rs[a] = merge(rs[a],b);
	swap(ls[a],rs[a]);
	return a;
}int main(){
	int n,q,x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&key[fa[i]=i]);
	scanf("%d",&q);
	while(q--){
		scanf("%s",op);
		if(op[0]=='M'){
			scanf("%d%d",&x,&y);
			if(d[x] || d[y])	continue;
			x = getfa(x);	y = getfa(y);
			if(x == y)	continue;
			fa[x] = fa[y] = merge(x,y);
		}else{
			scanf("%d",&x);
			if(d[x]){	printf("0\n");	continue;}
			d[x = getfa(x)] = 1;
			printf("%d\n",key[x]);
			fa[x] = merge(ls[x],rs[x]);
			fa[fa[x]] = fa[x];
		}
	}return 0;
}

• 相关文章