网上清一色的合并线段树题解，我又不会，只能自己胡来，没想到Rush过去了
永无乡包含 n 座岛，编号从 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。 Input
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。 对于 %的数据 n≤,q≤ 对于 %的数据 n≤,m≤n，q≤ Output
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-。 Sample Input Q
Q
B
B
Q
Q
Q
Sample Output
-
题意
这是一个只有建桥没有拆桥的操作，很显然可以离线重新排序，将之后会被建桥的区间连在一起，保证之后每次操作都是连续的一个区间。
然后发现就是维护一个区间K小，上主席树rush！rush！rush！就过了
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());
for(;isdigit(c);now=now*+c-'',c=getchar());return now;}
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = 1e5 + ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int N,M,K;
int val[maxn];
int nxt[maxn],ed[maxn];
int fa[maxn];
void init(){
For(i,,N){
ed[i] = i;
nxt[i] = -;
fa[i] = i;
}
}
int find(int p){
return p == fa[p]?p:fa[p] = find(fa[p]);
}
void Union(int p,int q){
int fp = find(p),fq = find(q);
if(fp == fq) return;
nxt[ed[fp]] = fq;
ed[fp] = ed[fq];
fa[fq] = fp;
}
struct Node{
int op,x,y;
Node(int op = ,int x = ,int y = ):op(op),x(x),y(y) {}
}node[];
int Index[maxn],tot;
int T[maxn],lson[maxn * ],rson[maxn * ],c[maxn * ];
int build(int l,int r){
int root = tot++;
c[root] = ;
if(l != r){
int m = (l + r) >> ;
lson[root] = build(l,m);
rson[root] = build(m + ,r);
}
return root;
}
int update(int root,int pos,int val){
int newroot = tot++,tmp = newroot;
c[newroot] = c[root] + val;
int l = ,r = N;
while(l < r){
int m = (l + r) >> ;
if(pos <= m){
lson[newroot] = tot++;
rson[newroot] = rson[root];
newroot = lson[newroot];
root = lson[root];
r = m;
}else{
rson[newroot] = tot++;
lson[newroot] = lson[root];
newroot = rson[newroot];
root = rson[root];
l = m + ;
}
c[newroot] = c[root] + val;
}
return tmp;
}
int query(int left_root,int right_root,int k){
int l = ,r = N;
while(l < r){
int m = (l + r) >> ;
if(c[lson[left_root]] - c[lson[right_root]] >= k){
r = m;
left_root = lson[left_root];
right_root = lson[right_root];
}else{
l = m + ;
k -= c[lson[left_root]] - c[lson[right_root]];
left_root = rson[left_root];
right_root = rson[right_root];
}
}
return l;
}
int id[maxn];
PII st[maxn];
int POS[maxn];
int main()
{
Sca2(N,M);
For(i,,N){
Sca(val[i]);
id[val[i]] = i;
}
init();
For(i,,M){
Sca2(st[i].fi,st[i].se);
Union(st[i].fi,st[i].se);
}
int K; Sca(K);
For(i,,K){
char op[]; scanf("%s",op);
Sca2(node[i].x,node[i].y);
if(op[] == 'B'){
node[i].op = ;
Union(node[i].x,node[i].y);
}else{
node[i].op = ;
}
}
int cnt = ;
For(i,,N){
if(i == fa[i]){
for(int j = i; ~j ; j = nxt[j]){
Index[++cnt] = j;
POS[j] = cnt;
}
}
}
T[N + ] = build(,N);
for(int i = N; i ; i --){
T[i] = update(T[i + ],val[Index[i]],);
}
init();
For(i,,M) Union(st[i].fi,st[i].se);
for(int i = ; i <= K ; i ++){
if(node[i].op == ){
Union(node[i].x,node[i].y);
}else{
int t = find(node[i].x);
int l = POS[t];
int r = POS[ed[t]];
int k = node[i].y;
//cout << l << " " << r << " " << k << endl;
if(k > r - l + || k < ){
puts("-1");
continue;
}
Pri(id[query(T[l],T[r + ],k)]);
}
}
#ifdef VSCode
system("pause");
#endif
return ;
}