qzh's Blog

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1200000
struct merge_heap{
    int l[M], r[M], d[M], value[M];
    void init(){
        memset(l, 0, sizeof(r));
        memset(r, 0, sizeof(r));
        memset(d, 1, sizeof(d));
    }
    int merge(int x, int y){
        if(!x) return y;
        if(!y) return x;
        if(value[x] > value[y]) swap(x, y);
        r[x] = merge(r[x], y);
        if(d[l[x]] < d[r[x]]){
            swap(l[x], r[x]);
        }
        d[x] = d[l[x]] + 1;
        return x;
    }
} wt;
int fa[M], tree[M], died[M];
int find(int x){
    if(fa[x] == x) return x;
    int k = find(fa[x]);
    fa[x] = k;
    return k;
}
int main(){
    int n, m;
    scanf("%d", &n);
    wt.init();
    for(int i = 1; i <= n; i ++){
        scanf("%d", &wt.value[i]);
        fa[i] = i;
        tree[i] = i;
    }
    scanf("%d", &m);
    char str[5];
    int a, b;
    for(int i = 1; i <= m; i ++){
        scanf("%s", str);
        if(str[0] == 'M'){
            scanf("%d%d", &a, &b);
            if(died[a] || died[b]) {
                continue;
            }
            if(find(a) != find(b)){
                int af = find(a), bf = find(b);
                fa[af] = bf;
                tree[bf] = wt.merge(tree[af], tree[bf]);
            }
        }
        else{
            scanf("%d", &a);
            if(died[a]){
                printf("0\n");
                continue;
            }
            int af = find(a);
            died[tree[af]] = 1;
            printf("%d\n", wt.value[tree[af]]);
            tree[af] = wt.merge(wt.l[tree[af]], wt.r[tree[af]]);
        }
    }
    return 0;
}