1 /**************************************************************  2     Problem: 1455  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:1316 ms  7     Memory:21312 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int N = 1000001; 15 int n, m, fa[N]; 16 bool died[N]; 17   18 struct heap{ 19     int v, l, r, dep; 20 }h[N]; 21   22 int Cnt; 23   24 inline int read(){ 25     int x = 0; 26     char ch = getchar(); 27     while (ch < ‘0‘ || ch > ‘9‘) 28         ch = getchar(); 29     while (ch >= ‘0‘ && ch <= ‘9‘){ 30         x = x * 10 + ch - ‘0‘; 31         ch = getchar(); 32     } 33     return x; 34 } 35   36 int pr[10], NUM = 0; 37 inline void print(int x){ 38     while (x) 39         pr[++NUM] = x % 10, x /= 10; 40     while (NUM) 41         putchar(pr[NUM--] + ‘0‘); 42     putchar(‘\n‘); 43 } 44   45 int find_fa(int x){ 46     return fa[x] == x ? x : fa[x] = find_fa(fa[x]); 47 } 48   49 inline int new_heap(int x){ 50     h[++Cnt].v = x; 51     h[Cnt].l = h[Cnt].r = h[Cnt].dep = 0; 52     return Cnt; 53 } 54   55 int Merge(int x, int y){ 56     if (!x || !y) return x + y; 57     if (h[x].v > h[y].v) 58         swap(x, y); 59     h[x].r = Merge(h[x].r, y); 60     if (h[h[x].l].dep < h[h[x].r].dep) 61         swap(h[x].l, h[x].r); 62     h[x].dep = h[h[x].r].dep + 1; 63     return x; 64 } 65   66 int Top(int x){ 67     return h[x].v; 68 } 69   70 int Pop(int x){ 71     return Merge(h[x].l, h[x].r); 72 } 73   74 int main(){ 75     n = read(); 76     int i, t, x, y; 77     for (i = 1; i <= n; ++i) 78         new_heap(read()), fa[i] = i; 79     h[0].dep = -1; 80     char ch; 81     m = read(); 82     for (i = 1; i <= m; ++i){ 83         ch = getchar(); 84         while (ch != ‘M‘ && ch != ‘K‘) ch = getchar(); 85         if (ch == ‘M‘){ 86             x = read(), y = read(); 87             if (died[x] || died[y]) continue; 88             x = find_fa(x), y = find_fa(y); 89             if (x != y) 90                 t = Merge(x, y), fa[x] = fa[y] = t; 91         }else{ 92             x = read(); 93             if (died[x]){ 94                 puts("0"); 95                 continue; 96             } 97             x = find_fa(x); 98             died[x] = 1; 99             print(h[x].v);100             fa[x] = Merge(h[x].l, h[x].r);101             fa[fa[x]] = fa[x];102         }103     }104     return 0;105 }