luoguP3224 [HNOI2012]永無鄉【線段樹,並查集】

語言: CN / TW / HK

洞庭青草,近中秋,更無一點風色。玉鑑瓊田三萬頃,著我扁舟一葉。素月分輝,明河共影,表裡俱澄澈。悠然心會,妙處難與君說。

應念嶺表經年,孤光自照,肝膽皆冰雪。短髮蕭騷襟袖冷,穩泛滄溟空闊。盡挹西江,細斟北斗,永珍為賓客。扣舷獨嘯,不知今夕何夕。

權值線段樹精巧飄飄有凌雲之氣,覺動態開點猶有塵心,巨大的空間負荷自軒轅而下,並查集依然不過輔助,島嶼連結之時,是樹嗎?不如說鏈的妥契。在遙遠的遠方,格陵蘭島傳說有一片永恆潔白之地,有人探尋過嗎?也許有,卻因感嘆至白之美而潸然以致不堪踏足半分。說來,古來成大事者,要麼白得坦蕩,有麼黑得徹骨,受欺負的永遠是老實人。這樣看來,踏上那片潔白的也只能是老實人了吧。

codes
# include "bits/stdc++.h"
using namespace std;
constexpr int N = 1e5 + 3;
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	struct node {
		int l, r, tot, id;
		// tot : due to the orderliness of the nodes of the weighted segment tree, the required ranking of sub tree nodes can be reflected by tot
	};
	vector<node> t(n * 2 * log2(n)); // it is said on the Internet that the spatial complexity of the dynamic open point weight line segment tree should be O(nlogn * 2)
	# define ls t[rt].l
	# define rs t[rt].r
	# define lson t[rt].l, l, mid
	# define rson t[rt].r, mid + 1, r
	auto push_up = [&](int rt) -> void {
		t[rt].tot = t[ls].tot + t[rs].tot;
	};
	int tree_index = 0;
	auto update = [&](auto update, int &rt, int l, int r, int x, int id) {
		if(!rt) rt = ++tree_index;
		if(l == r) {
			t[rt].id = id;
			++t[rt].tot;
			return;
		}
		int mid = l + r >> 1;
		if(x <= mid)
			update(update, lson, x, id);
		else
			update(update, rson, x, id);
		push_up(rt);
	};
	vector<int> fa(n + 1);
	vector<int> rt(n + 1);
	for(int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		update(update, rt[i], 1, n, x, i);
		fa[i] = i;
	}
	auto Find = [&](auto Find, int u) -> int {
		return u == fa[u] ? u : fa[u] = Find(Find, fa[u]);
	};
	auto merge = [&](auto merge, int x, int y, int l, int r) -> int {
		if(!x || !y) return x | y;
//		if(l == r) {)
// why (l == r) is impossible ? well, in this problem, the ranking of the islands has been determined, that is to say, it is guaranteed that the two islands will not rank the same
		int mid = l + r >> 1;
		t[x].l = merge(merge, t[x].l, t[y].l, l, mid);
		t[x].r = merge(merge, t[x].r, t[y].r, mid + 1, r);
		push_up(x);
		return x;
	};
	while(m--) {
		int x, y;
		cin >> x >> y;
		x = Find(Find, x), y = Find(Find, y);
		fa[y] = x;
		rt[x] = merge(merge, rt[x], rt[y], 1, n);
	}
	int q;
	cin >> q;
	while(q--) {
		char ch[9];
		cin >> ch;
//		char ch;
//		for(ch = '!'; ch!= 'Q' && ch != 'B'; ch = getchar());
//		 cout << ch << endl;
// HINT : there is a strange bug, in the case I use codes above and below, the second line of queries in the simple seems to be ignored. I don't know why
//		char ch = getchar();
//		while(ch != 'Q' && ch != 'B') ch = getchar();
//		cout << ch << endl;
		int x, y;
		if(ch[0] == 'B') { // represents the construction of a new bridge between island x and island y
			cin >> x >> y;
			x = Find(Find, x), y = Find(Find, y);
			if(x == y) continue;
			fa[y] = x;
			rt[x] = merge(merge, rt[x], rt[y], 1, n); // the change of root won't infuluence his childs, and of course, the information will be inherited
		}
		else { // it means to ask which of the islands connected to the island x is the island with the smallest importance ranking y
			cin >> x >> y;
			x = Find(Find, x);
			auto query = [&](auto query, int rt, int l, int r, int k) -> int {
				if(!rt || t[rt].tot < k) return 0;
				if(l == r) return t[rt].id;
				int mid = l + r >> 1;
				if(k <= t[ls].tot)
					return query(query, lson, k);
				else
					return query(query, rson, k - t[ls].tot); // if the left weight is less than the target, he will sacrifice to stop the seeker from moving to the right
			};
			int ans = query(query, rt[x], 1, n, y);
			ans == 0 ? cout << "-1\n" : cout << ans << "\n";
		}
	}
	return 0;
}
/*
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
*/