BZOJ1455 罗马游戏

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

#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", &n);
	for (int i = 1; i <= n; ++ i) {
		int w;
		scanf("%d", &w);
		nlst[i] = node(w, i);
		rt[i] = &nlst[i];
		al[i] = 1;
		r[i] = i;
	}
	scanf("%d", &m);
	while (m --) {
		char opt[3];
		int a, b;
		scanf("%s", opt);
		if (opt[0] == 'M') {
			scanf("%d%d", &a, &b);
			if (al[a] && 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", &a);
			if (!al[a])
				puts("0");
			else {
				a = getRoot(a);
				printf("%d\n", rt[a]-> vl);
				al[rt[a]-> id] = 0;
				rt[a] = pop(rt[a]);
			}
		}
	}
}