Description

罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人，每个人都是一个独立的团。最近举行了一次平面几何测试，每个人都得到了一个分数。 皇帝很喜欢平面几何，他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令： 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人，那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了，这条命令就忽略。 皇帝希望他每发布一条kill命令，下面的将军就把被杀的人的分数报上来。（如果这条命令被忽略，那么就报0分）
Input

第一行一个整数n（1<=n<=1000000）。n表示士兵数，m表示总命令数。 第二行n个整数，其中第i个数表示编号为i的士兵的分数。（分数都是[0..10000]之间的整数） 第三行一个整数m(1<=m<=100000) 第3+i行描述第i条命令。命令为如下两种形式： 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

解题方法： 左偏树裸题。。

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
struct tree{int l, r, v, dis, f;}heap[maxn]; //左儿子，右儿子，权值, 距离，父亲节点
int merge(int a, int b) //合并
{
    if(a == 0) return b;
    if(b == 0) return a;
    if(heap[a].v > heap[b].v) swap(a, b);
    heap[a].r = merge(heap[a].r, b);
    heap[heap[a].r].f = a;
    if(heap[heap[a].l].dis < heap[heap[a].r].dis) swap(heap[a].l, heap[a].r);
    if(heap[a].r == 0) heap[a].dis = 0;
    else heap[a].dis = heap[heap[a].r].dis + 1;
    return a;
}
int pop(int a){ //删除
    int l = heap[a].l, r = heap[a].r;
    heap[l].f = l, heap[r].f = r;
    heap[a].l = heap[a].r = heap[a].dis = 0;
    return merge(l, r);
}
int find(int a){ //查找
    return heap[a].f == a ? a : find(heap[a].f);
}
int die[maxn];
int main(){
    int n, m;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &heap[i].v);
        heap[i].l = heap[i].r = heap[i].dis = 0;
        heap[i].f = i;
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++){
        char cmd[10];
        int x, y;
        scanf("%s", cmd);
        if(cmd[0] == 'M'){
            scanf("%d%d", &x, &y);
            if(die[x] || die[y]) continue;
            int fx = find(x), fy = find(y);
            if(fx != fy){
                int t = merge(fx, fy);
                heap[fx].f = heap[fy].f = t;
            }
        }
        else{
            scanf("%d", &x);
            if(die[x]) printf("0\n");
            else{
                int fx = find(x);
                die[fx] = 1;
                printf("%d\n", heap[fx].v);
                heap[fx].f = merge(heap[fx].l, heap[fx].r);
                heap[heap[fx].f].f = heap[fx].f;
            }
        }
    }
    return 0;
}