洞庭青草，近中秋，更无一点风色。玉鉴琼田三万顷，着我扁舟一叶。素月分辉，明河共影，表里俱澄澈。悠然心会，妙处难与君说。
应念岭表经年，孤光自照，肝胆皆冰雪。短发萧骚襟袖冷，稳泛沧溟空阔。尽挹西江，细斟北斗，万象为宾客。扣舷独啸，不知今夕何夕。
权值线段树精巧飘飘有凌云之气，觉动态开点犹有尘心，巨大的空间负荷自轩辕而下，并查集依然不过辅助，岛屿连结之时，是树吗？不如说链的妥契。在遥远的远方，格陵兰岛传说有一片永恒洁白之地，有人探寻过吗？也许有，却因感叹至白之美而潸然以致不堪踏足半分。说来，古来成大事者，要么白得坦荡，有么黑得彻骨，受欺负的永远是老实人。这样看来，踏上那片洁白的也只能是老实人了吧。
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 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
*/
__EOF__
作 者：bingoyes
出 处：https://www.cnblogs.com/bingoyes/p/16586642.html
关于博主：编程路上的小学生，热爱技术，喜欢专研。评论和私信会在第一时间回复。或者直接私信我。
版权声明：署名 - 非商业性使用 - 禁止演绎，协议普通文本 | 协议法律文本。
声援博主：如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。您的鼓励是博主的最大动力！