BZOJ1455:罗马游戏【斜堆】

dzy posted @ 2013年12月09日 20:09 in BZOJ with tags bzoj 斜堆 , 1978 阅读

要求维护一个数据结构,支持:

(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;
}
Avatar_small
pavzi.com 说:
2024年1月09日 14:42

Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter