永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。
Input
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000 对于 100%的数据 n≤100000,m≤n，q≤300000
Output
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
Sample Input
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
Sample Output
-1
2
5
1
2
题目大意 给出n个点和m条边，每个点有个点权，范围为1 ~ n，且没有重复。操作有两种，第一种是联通两个点，第二种是查询点i所在的连通块内第k小的点的编号。
显然会用到并查集，显然线段树合并。
然后我来讲讲线段树合并的时间复杂度证明。
一次线段树合并的实际代价是减少的节点个数。
开始有$O(n\log n)$个节点，最后只有$O(n)$个点，所以时间复杂度为$O(n\log n)$。
Code
/**
* bzoj
* Problem#2733
* Accepted
* Time:2352ms
* Memory:26304k
*/
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <stack>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean;
const signed int inf = (signed)((1u << ) - );
const signed long long llf = (signed long long)((1ull << ) - );
const double eps = 1e-;
const int binary_limit = ;
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
template<typename T>
inline boolean readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -) {
ungetc(x, stdin);
return false;
}
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u * ) + x - '');
ungetc(x, stdin);
u *= aFlag;
return true;
} typedef class SegTreeNode {
public:
int s;
SegTreeNode *l, *r; SegTreeNode():s(), l(NULL), r(NULL) { }
SegTreeNode(int s, SegTreeNode* l, SegTreeNode* r):s(s), l(l), r(r) { } inline void pushUp() {
s = l->s + r->s;
}
}SegTreeNode; #define Limit 2000000
SegTreeNode pool[Limit];
int top = ;
SegTreeNode null = SegTreeNode(, &null, &null); inline SegTreeNode* newnode() {
if(top >= Limit) {
return new SegTreeNode(, &null, &null);
}
pool[top].l = &null, pool[top].r = &null;
return pool + (top++);
} #define null &null typedef class union_found {
public:
int* f;
SegTreeNode** rts; union_found():f(NULL), rts(NULL) { }
union_found(int n, int* lis) {
f = new int[(const int)(n + )];
rts = new SegTreeNode*[(n + )];
for(int i = ; i <= n; i++)
f[i] = i;
for(int i = ; i <= n; i++) {
rts[i] = null;
update(rts[i], , n, lis[i]);
}
} void update(SegTreeNode*& node, int l, int r, int idx) {
if(node == null) node = newnode();
if(l == idx && r == idx) {
node->s++;
return;
}
int mid = (l + r) >> ;
if(idx <= mid) update(node->l, l, mid, idx);
else update(node->r, mid + , r, idx);
node->pushUp();
} void merge(SegTreeNode*& a, SegTreeNode*& b) { // Make segment tree b into a.
if(b == null)
return;
if(a == null) {
a = b;
return;
}
a->s += b->s;
merge(a->l, b->l);
merge(a->r, b->r);
a->pushUp();
} int kth(SegTreeNode* node, int l, int r, int k) {
if(node == null)
return -;
if(l == r && k == )
return l;
int ls = node->l->s, mid = (l + r) >> ;
if(k <= ls)
return kth(node->l, l, mid, k);
else
return kth(node->r, mid + , r, k - ls);
} int find(int x) {
return (f[x] == x) ? (x) : (f[x] = find(f[x]));
} void unit(int fa, int so) {
if(isConnected(fa, so)) return;
int ffa = find(fa);
int fso = find(so);
merge(rts[ffa], rts[fso]);
f[fso] = ffa;
} boolean isConnected(int a, int b) {
return find(a) == find(b);
} int query(int x, int n, int k) {
return kth(rts[find(x)], , n, k);
}
}union_found; int n, m, q;
int* imp;
int* keyer;
union_found uf; inline void init() {
readInteger(n);
readInteger(m);
imp = new int[(n + )];
keyer = new int[(n + )];
for(int i = ; i <= n; i++)
readInteger(imp[i]), keyer[imp[i]] = i;
uf = union_found(n, imp);
for(int i = , a, b; i <= m; i++) {
readInteger(a);
readInteger(b);
uf.unit(a, b);
}
} inline void solve() {
readInteger(q);
char buf[];
int a, b;
while(q--) {
scanf("%s%d%d", buf, &a, &b);
if(buf[] == 'B') {
uf.unit(a, b);
} else {
int res = uf.query(a, n, b);
if(res == -)
puts("-1");
else
printf("%d\n", keyer[res]);
}
}
} int main() {
init();
solve();
return ;
}