[文章目录]
Description
罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人，每个人都是一个独立的团。最近举行了一次平面几何测试，每个人都得到了一个分数。 皇帝很喜欢平面几何，他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令： 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人，那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了，这条命令就忽略。 皇帝希望他每发布一条kill命令，下面的将军就把被杀的人的分数报上来。（如果这条命令被忽略，那么就报0分）1<=n<=1000000 1<=m<=100000
可并堆裸题。拍左偏树。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,fa[1001000];
bool die[1001000];
struct heap {
int ls,rs,w,npl;
};
heap he[1001000];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(he[x].w>he[y].w) swap(x,y);
he[x].rs=merge(he[x].rs,y);
if(he[he[x].rs].npl>he[he[x].ls].npl) swap(he[x].ls,he[x].rs);
he[x].npl=he[he[x].rs].npl+1;
return x;
}
void pop(int x)
{
printf("%d\n",he[x].w); die[x]=1;
fa[he[x].ls]=fa[he[x].rs]=fa[x]=merge(he[x].ls,he[x].rs);
}
inline int read(int &x)
{
x=0; char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
int main()
{
scanf("%d",&n); int i,x;
for(i=1;i<=n;++i)
{
read(x); fa[i]=i;
he[i].w=x; he[i].npl=1;
}
int m,y; char sw[10]; scanf("%d",&m);
while(m--)
{
scanf("%s",sw);read(x);
if(sw[0]=='M')
{
read(y);
if(die[x]||die[y]) continue;
x=find(x); y=find(y); if(x==y) continue;
fa[x]=fa[y]=merge(x,y);
}
else
{
if(die[x]) {puts("0"); continue;}
x=find(x); pop(x);
}
}
return 0;
}