@[Frightened](/user/347589) 并查集没有路径压缩。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define srand srand(time(NULL))
#define random(x) rand() % (x)
#define il inline
#define ptc putchar
#define reg register
#define mp make_pair
typedef __int128 LL;
typedef long long ll;
typedef pair<int, int> PII;
namespace cyyh {
template <typename T>
il void read(T &x) {
x = 0; T f = 1; char ch;
while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar(); x *= f;
}
template <typename T, typename ...L>
il void read(T &x, L &...y) {read(x); read(y...);}
template <typename T>
il void write(T x) {
if (x < 0) ptc('-'), x = -x;
if (x > 9) write(x / 10);
ptc(x % 10 + '0');
}
}
using namespace cyyh;
const int N = 1e5 + 5;
int n, m, q, fa[N], tot, root[N], sum[N * 900], ls[N * 900], rs[N * 900];
int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}
void Merge(int x, int y) {fa[Find(y)] = Find(x);}
void build(int l, int r, int x, int &id) {
id = ++tot;
if (l == r) return ++sum[id], void();
int mid = l + r >> 1;
if (x <= mid) build(l, mid, x, ls[id]);
else build(mid + 1, r, x, rs[id]);
sum[id] = sum[ls[id]] + sum[rs[id]];
}
void modify(int l, int r, int &id1, int &id2) {
if (!id1) id1 = ++tot;
if (l == r) {
sum[id1] += sum[id2];
return ;
}
int mid = l + r >> 1;
if (!rs[id1] && rs[id2]) rs[id1] = rs[id2];
else if (rs[id1] && rs[id2]) modify(mid + 1, r, rs[id1], rs[id2]);
if (!ls[id1] && ls[id2]) ls[id1] = ls[id2];
else if (ls[id1] && ls[id2]) modify(l, mid, ls[id1], ls[id2]);
sum[id1] = sum[ls[id1]] + sum[rs[id1]];
}
int query(int l, int r, int k, int id) {
if (l == r) return l;
int mid = l + r >> 1;
if (sum[ls[id]] >= k) return query(l, mid, k, ls[id]);
else return query(mid + 1, r, k - sum[ls[id]], rs[id]);
}
map <int, int> num;
int main() {
read(n, m);
for (int i = 1; i <= n; ++i) {
int x;
fa[i] = i, read(x), num[x] = i;
build(1, N, x, root[i]);
}
// modify(1, N, root[1], root[2]);
// modify(1, N, root[1], root[5]);
for (int i = 1; i <= m; ++i) {
int u, v;
read(u, v);
modify(1, N, root[Find(u)], root[Find(v)]);
Merge(u, v);
}
// cout << Find(2) << "!" << endl;
read(q);
while (q--) {
char op; int x, y;
cin >> op; read(x, y);
if (op == 'B') modify(1, N, root[Find(x)], root[Find(y)]), Merge(x, y);
else {
int ans = num[query(1, N, y, root[Find(x)])];
if (!ans) puts("-1");
else write(ans), ptc('\n');
}
}
return 0;
}
```
by AIskeleton @ 2022-03-10 13:38:21
@[AIskeleton](/user/540715) 谢谢!
by Zelotz @ 2022-03-10 16:20:53