```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=200010;
int n,m,seq=1,rt[MAXN],fa[100005];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unionn(int x,int y){
int a=find(x),b=find(y);
if(a!=b)fa[b]=a;
return;
}
ll val[MAXN<<6];
struct segment{
int space[MAXN<<5],ch[MAXN<<5][2],tot=0,cnt=0;
void push_up(int cur){
val[cur]=val[ch[cur][0]]+val[ch[cur][1]];
}
int new_node(){int nd=cnt?space[cnt--]:++tot;val[nd]=ch[nd][0]=ch[nd][1]=0;return nd;}
void del_node(int p) {
space[++cnt]=p,ch[p][0]=ch[p][1]=val[p]=0;
return;
}
void update(int &p,int l,int r,int pos,int v) {
if (!p){p=new_node();}
val[p]+=v;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)update(ch[p][0],l,mid,pos,v);
else update(ch[p][1],mid+1,r,pos,v);
push_up(p);
return;
}
ll query(int p,int l,int r,int xl,int xr){
if(xr<l||r<xl)return 0;
if(xl<=l&&r<=xr)return val[p];
int mid=(l+r)>>1;
return query(ch[p][0],l,mid,xl,xr)+query(ch[p][1],mid+1,r,xl,xr);
}
int kth(int p,int l,int r,int k) {
if(l==r)return l;
int mid=(l+r)>>1;
if(val[ch[p][0]]>=k)return kth(ch[p][0],l,mid,k);
else return kth(ch[p][1],mid+1,r,k-val[ch[p][0]]);
}
void merge(int &x,int &y){
if(!x||!y){
if(!x)x=y;
return;
}
val[x]+=val[y];
merge(ch[x][0],ch[y][0]);
merge(ch[x][1],ch[y][1]);
del_node(y);
push_up(x);
push_up(y);
}
};
segment tree;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
fa[i]=i;
tree.update(rt[i],1,n,x,1);
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
unionn(x,y);
tree.merge(rt[find(x)],rt[find(y)]);
}
for(int i=1;i<=n;i++)cout<<find(i)<<' '<<rt[i]<<'\n';
int q;
cin>>q;
for(int i=1;i<=q;i++){
string a;
int x,y;
cin>>a;
cin>>x>>y;
if(a=="B"){
unionn(x,y);
tree.merge(rt[find(x)],rt[find(y)]);
}
else{
int ans=tree.kth(rt[find(x)],1,n,y);
cout<<(ans==0?-1:ans)<<'\n';
}
}
}
```
by Forever1507 @ 2021-11-10 10:31:33
草真的没有好心人吗
by Forever1507 @ 2021-11-10 10:41:37