【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;
}