bzoj 1455:ローマゲーム(並積み可能)

1455:ローマゲーム

Time Limit: 5 Sec  
Memory Limit: 64 MB
Submit: 1346  
Solved: 557
[ Submit][ Status][ Discuss]

Description

ローマ皇帝は殺人ゲームが大好きです.彼の軍隊にはn人がいて、誰もが独立した団です.最近平面幾何学のテストが行われ、誰もが点数を取った.皇帝は平面幾何学が大好きで、得点の低い人に鼻をついて笑った.彼はこのようなゲームをすることにした.2つのコマンドを発行できます.1.Merger(i, j).iのいる団とjのいる団を一つの団にまとめる.i,jが死んだ人がいる場合は,その命令を無視する.2. Kill(i).iのいる団の中で最も得点の低い人を殺す.もしiという人が死んだら、この命令は無視します.皇帝は彼がkill命令を出すたびに、次の将軍が殺された人の点数を報告することを望んでいる.(このコマンドが無視された場合、0点を報告します)

Input

1行目の整数n(1<=n<=1000000).nは兵士数,mは総命令数を表す.2行目のn個の整数で、i番目の数はi番の兵士の点数を表す.3行目の整数m(1<=m<=10000000)3+i行目は、i番目のコマンドを記述する.コマンドは次の2つの形式です.1.M i j 2. K i

Output

命令がKillなら、対応するのは殺された点数を出力してください.(この人がいなければ0を出力)

Sample Input

5 100 90 66 99 10 7 M 1 5 K 1 K 1 M 2 3 M 3 4 K 5 K 4

Sample Output

10 100 0 66

HINT

Source

[ Submit][ Status][ Discuss]
标题解:左偏樹
左バイアスツリーの性質:基本構造は斜めスタックに似ています
1.【スタックの性質】:ノードのキーワードはその子ノードのキーワードに等しい
2.【左寄りの性質】:ノードから最も近いリーフノードまでの距離をノード距離と定義し、任意のノードの左の息子の距離が右の息子の距離より大きい
左偏樹は挿入操作を実現する際に常に右側から挿入し,すなわち常に短い側を成長させ,右側が左側より長ければ左右側を交換し,右側から成長を続ける

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1000003
using namespace std;
int n,m,a[N],fa[N];
int lch[N],rch[N],d[N],mark[N];
int find(int x)
{
	if (fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
int merge(int x,int y)
{
	if (!x) return y;
	if (!y) return x;
	if (a[x]>a[y]) swap(x,y);
	rch[x]=merge(rch[x],y);
	if (d[lch[x]]<d[rch[x]])
	 swap(lch[x],rch[x]);
	d[x]=d[rch[x]]+1;
	return x;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	  scanf("%d",&a[i]),fa[i]=i;
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
	   int x,y; char s[10];
	   scanf("%s",s);
	   if (s[0]=='M')
	    {
	    	scanf("%d%d",&x,&y);
	    	if (mark[x]||mark[y]) continue;
	    	int r1=find(x); int r2=find(y);
	    	if (r1!=r2)
	    	 {
	    	 	int t=merge(r1,r2);
	    	 	fa[r1]=fa[r2]=t;
	    	 }
	    }
	   else
	    {
	    	scanf("%d",&x);
	    	if (mark[x]) 
	    	{
	    		printf("0
");
	    	    continue;
	    	}
	    	int now=find(x); mark[now]=1;
	    	printf("%d
",a[now]);
	    	fa[now]=merge(lch[now],rch[now]);
	    	fa[fa[now]]=fa[now];
	    }
	}
}