用并查集维护联通性。对每个联通块维护一个平衡树。合并时启发式合并。比较懒，用了pb_ds。
1 #include<cstdio>
2 #include<ext/pb_ds/assoc_container.hpp>
3 #include<ext/pb_ds/tree_policy.hpp>
4 using namespace std;
5 using namespace __gnu_cxx;
6 using namespace __gnu_pbds;
7 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T[100001];
8 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>::iterator it;
9 int num[100001],val[100001],fa[100001],rank[100001];
10 int n,m,q,x,y,f1,f2;
11 char op[2];
12 int Res,Num;char C,CH[20];
13 inline int G()
14 {
15 Res=0;C='*';
16 while(C<'0'||C>'9')C=getchar();
17 while(C>='0'&&C<='9'){Res=Res*10+(C-'0');C=getchar();}
18 return Res;
19 }
20 inline void P(int x)
21 {
22 Num=0;while(x>0)CH[++Num]=x%10,x/=10;
23 while(Num)putchar(CH[Num--]+48);
24 putchar('\n');
25 }
26 void init()
27 {
28 for(int i=1;i<=n;i++)
29 fa[i]=i;
30 }
31 int findroot(int x)
32 {
33 if(fa[x]==x)
34 return x;
35 int rt=findroot(fa[x]);
36 fa[x]=rt;
37 return rt;
38 }
39 void Union(const int &u,const int &v)
40 {
41 if(rank[u]<rank[v])
42 {
43 fa[u]=v;
44 for(it=T[u].begin();it!=T[u].end();it++)
45 T[v].insert((*it));
46 T[u].clear();
47 }
48 else
49 {
50 fa[v]=u;
51 for(it=T[v].begin();it!=T[v].end();it++)
52 T[u].insert((*it));
53 T[v].clear();
54 if(rank[u]==rank[v]) rank[u]++;
55 }
56 }
57 int main()
58 {
59 n=G();m=G();
60 init();
61 for(int i=1;i<=n;i++)
62 {
63 val[i]=G();
64 T[i].insert(val[i]);
65 num[val[i]]=i;
66 }
67 for(int i=1;i<=m;i++)
68 {
69 x=G();y=G();
70 f1=findroot(x),f2=findroot(y);
71 if(f1!=f2) Union(f1,f2);
72 }
73 q=G();
74 for(int i=1;i<=q;i++)
75 {
76 scanf("%s",op);x=G();y=G();
77 if(op[0]=='Q')
78 {
79 f1=findroot(x);
80 if(T[f1].size()<y) puts("-1");
81 else P(num[*T[f1].find_by_order(y-1)]);
82 }
83 else
84 {
85 f1=findroot(x),f2=findroot(y);
86 if(f1!=f2) Union(f1,f2);
87 }
88 }
89 return 0;
90 }