<div class="post_brief"><p>
左偏树+并查集的一眼题嘛。然后合并的时候搞忘了如果两个人已经在同一个团里要跳过，于是左偏树自交去了。</p>

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


#define szof(p) ((p)?(p->sz):0)
struct node {
int sz, vl, id;
node *ls, rs;
node() {}
node(int v, int i) {
vl = v;
id = i;
sz = 1;
ls = rs = 0;
}
inline void update() {
if (szof(ls) < szof(rs))
swap(ls, rs);
}
};
node merge(node p, node q) {
if (!p)
return q;
else if (!q)
return p;
else if (p-> vl < q-> vl) {
p-> rs = merge(p-> rs, q);
p-> update();
return p;
}
else {
q-> rs = merge(q-> rs, p);
q-> update();
return q;
}
}
node pop(node p) {
if (p)
return merge(p-> ls, p-> rs);
else
return 0;
}


const int maxn = 1000009;


int n, m, r[maxn];
bool al[maxn];
node nlst[maxn], *rt[maxn];


int getRoot(int x) {
register int p, q;
for (p = r[x]; p ^ r[p]; p = r[p]);
for (; x ^ p; q = r[x], r[x] = p, x = q);
return x;
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d", &amp;n);
for (int i = 1; i &lt;= n; ++ i) {
	int w;
	scanf("%d", &amp;w);
	nlst[i] = node(w, i);
	rt[i] = &amp;nlst[i];
	al[i] = 1;
	r[i] = i;
}
scanf("%d", &amp;m);
while (m --) {
	char opt[3];
	int a, b;
	scanf("%s", opt);
	if (opt[0] == 'M') {
		scanf("%d%d", &amp;a, &amp;b);
		if (al[a] &amp;&amp; al[b]) {
			a = getRoot(a);
			b = getRoot(b);
			if (a == b)
				continue;
			r[a] = b;
			rt[b] = merge(rt[b], rt[a]);
		}
	}
	else if (opt[0] == 'K') {
		scanf("%d", &amp;a);
		if (!al[a])
			puts("0");
		else {
			a = getRoot(a);
			printf("%d\n", rt[a]-&gt; vl);
			al[rt[a]-&gt; id] = 0;
			rt[a] = pop(rt[a]);
		}
	}
}



}