【ybt金牌导航4-1-2】【luogu P2713】合并游戏 / 罗马游戏

合并游戏 / 罗马游戏

题目链接：ybt金牌导航4-1-2 / luogu P2713

题目大意

有一个序列，一开始各自在各自的集合中。

你要支持两个操作，把两个数所在的集合合并，求出一个数所在集合中最小的数并把它删除。

如果询问的数已经被删除，那就直接跳过。（求最小数就还要输出 0 0 0）

思路

看到求集合中最小，自然想到线段树，这个那个树之类的。

但你你又看到合并集合，那就是左偏树。

那你就记录一下左偏树上的这个点代表数列的哪个数，然后从键值是从小到大，然后就搞合并和删除两个操作。

然后置于你删除的数在哪个集合就搞个并查集维护一下就好了。

记得判断这个点是否被删除，如果删除就直接是跳过。

当然如何合并操作中的两个点已经在同一个集合，就不用合并了。

代码

#include<cstdio>
#include<algorithm>

using namespace std;

struct left_tree {
	int x, l, r, dis, dy;
}a[1000001];
int n, m, fa[1000001], x, y, root[1000001];
int dead[1000001];
char c;

int find(int now) {
	if (fa[now] == now) return now;
	return fa[now] = find(fa[now]);
}

int merge(int x, int y) {
	if (!x) return y;
	if (!y) return x;
	
	if (a[x].x > a[y].x) swap(x, y);
	a[x].r = merge(a[x].r, y);
	if (a[a[x].r].dis > a[a[x].l].dis) swap(a[x].l, a[x].r);
	a[x].dis = a[a[x].r].dis + 1;
	
	return x;
}

int delete_top(int x) {
	return merge(a[x].l, a[x].r);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i].x);
		a[i].dy = i;
		root[i] = i;
		fa[i] = i;
	}
	
	scanf("%d", &m);
	while (m--) {
		c = getchar();
		while (c != 'M' && c != 'K') c = getchar();
		
		if (c == 'M') {
			scanf("%d %d", &x, &y);
			if (dead[x] || dead[y]) continue;//已经死了其中一个
			int X = find(x), Y = find(y);
			if (X == Y) continue;//已经合并了
			fa[X] = Y;
			root[Y] = merge(root[X], root[Y]);
		}
		else {
			scanf("%d", &x);
			int X = find(x);
			if (dead[x]) printf("0\n");//这个人已近死了
				else {
					printf("%d\n", a[root[X]].x);
					dead[a[root[X]].dy] = 1;//标记这个人被杀死
					root[X] = delete_top(root[X]);
				}
		}
	}
	
	return 0;
}