【BZOJ1455】罗马游戏（左偏树）

题面

BZOJ

然而权限题。

题解

左偏树模板题。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 1000100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

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

	return t?-x:x;

}

struct Node{int v,fa,ls,rs,dis;}t[MAX];

int n,m;

char ch[MAX];

int getf(int x)

{

	while(t[x].fa)

		x=t[x].fa;

	return x;

}

int Merge(int r1,int r2)

{

	if(!r1||!r2)return r1|r2;

	if(t[r1].v>t[r2].v)swap(r1,r2);

	t[r1].rs=Merge(t[r1].rs,r2);

	t[t[r1].rs].fa=r1;

	if(t[t[r1].rs].dis>t[t[r1].ls].dis)swap(t[r1].ls,t[r1].rs);

	t[r1].dis=t[t[r1].rs].dis+1;

	return r1;

}

void pop(int x)

{

	t[t[x].ls].fa=t[t[x].rs].fa=0;

	t[x].v=-1;

	Merge(t[x].ls,t[x].rs);

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)t[i].v=read();

	m=read();

	while(m--)

	{

		scanf("%s",ch);

		if(ch[0]=='M')

		{

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

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

			if(getf(x)!=getf(y))Merge(getf(x),getf(y));

		}

		else

		{

			int x=read();

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

			x=getf(x);printf("%d\n",t[x].v);

			pop(x);

		}

	}

	return 0;

}