```
#include<bits/stdc++.h>
using namespace std;
struct data
{
int l,r,sum;
}t[3000500];
int n;
int m;
int total;
int id[100500];
int temp[100500];
int s1[100500];
int find(int x)
{
if(x==s1[x])
{
return x;
}
s1[x]=find(s1[x]);
return s1[x];
}
int build(int l,int r,int x)
{
int o=++total;
if(l==r)
{
t[o].sum=1;
return o;
}
int mid=(l+r)/2;
if(x<=mid)
{
t[o].l=build(l,mid,x);
}
else
{
t[o].r=build(mid+1,r,x);
}
t[o].sum=t[t[o].l].sum+t[t[o].r].sum;
return o;
}
int update(int total1,int total2,int l,int r)
{
if(total1==0)
{
return total2;
}
if(total2==0)
{
return total1;
}
if(l==r)
{
t[total1].sum+=t[total2].sum;
return total1;
}
int mid=(l+r)/2;
t[total1].l=update(t[total1].l,t[total2].l,l,mid);
t[total1].r=update(t[total1].r,t[total2].r,mid+1,r);
t[total1].sum=t[t[total1].l].sum+t[t[total1].r].sum;
return total1;
}
int query(int total1,int l,int r,int k)
{
if(l==r)
{
return l;
}
int mid=(l+r)/2;
int s=t[t[total1].l].sum;
if(k<=s)
{
return query(t[total1].l,l,mid,k);
}
else
{
return query(t[total1].r,mid+1,r,k-s);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
temp[i]=build(1,n,x);
id[x]=i;
s1[i]=i;
}
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
int total1=find(u);
int total2=find(v);
if(total1==total2)
{
continue;
}
s1[total2]=total1;
temp[total1]=update(temp[total1],temp[total2],1,n);
}
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
char c[10];
int u,v;
scanf("%s%d%d",c,&u,&v);
if(c[0]=='B')
{
int total1=find(u);
int total2=find(v);
if(total1==total2)
{
continue;
}
s1[total2]=total1;
temp[total1]=update(temp[total1],temp[total2],1,n);
}
else
{
int total1=find(u);
if(t[temp[total1]].sum<v)
{
printf("-1\n");
}
else
{
int k=query(temp[total1],1,n,v);
printf("%d\n",id[k]);
}
}
}
return 0;
}
```
by Vuglar_zuo @ 2023-08-10 15:49:49