【BZOJ1455】羅馬遊戲

【題目連結】

• 點選打開連結

【思路要點】

• 可并堆模闆題。

【代碼】

#include<bits/stdc++.h>
using namespace std;
#define MAXN	1000005
struct Node {
	int father, value;
	int child[2], depth[2];
};
int n, m;
Node a[MAXN];
bool killed[MAXN];
int merge(int x, int y) {
	if (x == 0) return y;
	if (y == 0) return x;
	if (a[x].value > a[y].value) swap(x, y);
	a[x].child[1] = merge(a[x].child[1], y);
	a[a[x].child[1]].father = x;
	a[x].depth[1] = 1 + max(a[a[x].child[1]].depth[0], a[a[x].child[1]].depth[1]);
	if (a[x].depth[1] > a[x].depth[0]) {
		swap(a[x].child[0], a[x].child[1]);
		swap(a[x].depth[0], a[x].depth[1]);
	}
	return x;
}
int root(int x) {
	if (a[x].father == 0) return x;
	else return root(a[x].father);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i].value);
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		char opt;
		scanf("\n%c", &opt);
		if (opt == 'M') {
			int x, y;
			scanf("%d%d", &x, &y);
			if (killed[x] || killed[y]) continue;
			int tmp = root(x), tnp = root(y);
			if (tmp == tnp) continue;
			else merge(tmp, tnp);
		} else {
			int x;
			scanf("%d", &x);
			if (killed[x]) {
				printf("0\n");
				continue;
			}
			int tmp = root(x);
			printf("%d\n", a[tmp].value);
			killed[tmp] = true;
			a[merge(a[tmp].child[0], a[tmp].child[1])].father = 0;
		}
	}
	return 0;
}