BZOJ1455：罗马游戏

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=1455

浅谈左偏树：https://www.cnblogs.com/AKMer/p/10246635.html

左偏树模板题。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+5;

int n,m;

int son[maxn][2];

int v[maxn],fa[maxn],dist[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

int find(int x) {

	while(fa[x])x=fa[x];

	return x;

}

int merge(int a,int b) {

	if(!a||!b)return a+b;

	if(v[a]>v[b])swap(a,b);

	son[a][1]=merge(son[a][1],b);

	fa[son[a][1]]=a;

	if(dist[son[a][1]]>dist[son[a][0]])

		swap(son[a][1],son[a][0]);

	dist[a]=dist[son[a][1]]+1;

	return a;

}

void pop(int u) {

	printf("%d\n",v[u]);v[u]=-1;

	fa[son[u][0]]=fa[son[u][1]]=0;

	merge(son[u][0],son[u][1]);

	son[u][0]=son[u][1]=0;

}

int main() {

	n=read();

	for(int i=1;i<=n;i++)

		v[i]=read();

	m=read();

	for(int i=1;i<=m;i++) {

		char s[10];

		scanf("%s",s+1);

		if(s[1]=='M') {

			int x=read(),y=read();

			if(v[x]==-1||v[y]==-1)continue;

			x=find(x),y=find(y);

			if(x==y)continue;

			merge(x,y);

		}

		else {

			int u=read();

			if(v[u]==-1) {puts("0");continue;}

			u=find(u),pop(u);

		}

	}

	return 0;

}

巴特西

BZOJ1455：罗马游戏

最新文章

热门文章