题解
并查集，然后利用启发式合并最多带来一个$log$的代价，暴力拆treap，然后合并。
时间复杂度$O(nlog^2 n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
using namespace std;
typedef long long ll;
struct Tr{
Tr *ch[2];
int r,v,siz,cnt,id;
int cmp(int x) const {
if(x==v)return -1;
return x>v;
}
void maintain(){
siz=cnt;
if(ch[0]!=NULL)siz+=ch[0]->siz;
if(ch[1]!=NULL)siz+=ch[1]->siz;
}
};
Tr tree[1700005],*pos[400005],*root;
int S=0,n,m;
int par[100005],rk[100005];
void rorate_tr(Tr* &tr,int d){
Tr *k=tr->ch[d^1];
tr->ch[d^1]=k->ch[d];
k->ch[d]=tr;
tr->maintain(),k->maintain(),tr=k;
}
void insert_tr(Tr* &tr,int x,int i_){
if(tr==NULL){
S++,tr=&tree[S],tr->siz=1,tr->cnt=1,tr->v=x;
tr->ch[0]=tr->ch[1]=NULL,tr->r=rand();
tr->id=i_;
return ;
}
tr->siz++;
if(tr->v==x){
tr->cnt++;
}else{
int d=tr->cmp(x);
insert_tr(tr->ch[d],x,i_);
if(tr->ch[d]->r>tr->r)rorate_tr(tr,d^1);
}
}
int Kth(Tr *tr,int x){
if(tr==NULL||x<=0||x>tr->siz)return -1;
int evid=(tr->ch[0]==NULL)?0:tr->ch[0]->siz;
if(x<=evid)return Kth(tr->ch[0],x);
else if(x>evid+tr->cnt)return Kth(tr->ch[1],x-evid-tr->cnt);
else return tr->id;
}
int Find(int t){
if(par[t]==t)return t;
else return (par[t]=Find(par[t]));
}
int unite(int a,int b){
int x=Find(a),y=Find(b);
if(x==y)return -1;
if(rk[x]>rk[y]){
par[y]=x;
return x;
}else {
par[x]=y;
if(rk[x]==rk[y])rk[y]++;
return y;
}
}
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
void dfs(Tr *t){
if(t==NULL)return ;
insert_tr(root,t->v,t->id);
dfs(t->ch[0]),dfs(t->ch[1]);
}
void MMerge(int x,int y){
if(Find(x)==Find(y))return ;
int ss=Find(x),tt=Find(y);
int res=unite(x,y);//大的
if(res==tt)root=pos[tt],dfs(pos[ss]),pos[tt]=root;
else root=pos[ss],dfs(pos[tt]),pos[ss]=root;
}
void init(){
n=read(),m=read();
int pri,u,v;
for(int i=1;i<=n;i++)
par[i]=i,rk[i]=0,pri=read(),
insert_tr(pos[i],pri,i);
for(int i=1;i<=m;i++){
u=read(),v=read();
MMerge(u,v);
}
}
void solve(){
int q=read(),x,y;
char ord[3];
while(q--){
scanf("%s%d%d",ord,&x,&y);
if(ord[0]=='B')MMerge(x,y);
else printf("%d\n",Kth(pos[Find(x)],y));
}
}
int main(){
init();
solve();
return 0;
}