```cpp
#include<bits/stdc++.h>
using namespace std;
struct Point{
int l,r,siz,rnd;
int val,k;//k is id
};
#define N 100001
struct fhqTreap{
private:
Point q[N];
int nw,root[N],rootX,rootY,fa[N];
int New(int val,int k){
q[++nw].val=val;
q[nw].k=k;
q[nw].siz=1;
q[nw].rnd=rand();
return nw;
}
void Update(int id){
q[id].siz=q[q[id].l].siz+q[q[id].r].siz+1;
}
void Split(int id,int key,int &idX,int &idY){
if(id==0) idX=idY=0;
else{
if(q[id].val<=key){
idX=id;
Split(q[id].r,key,q[id].r,idY);
}
else{
idY=id;
Split(q[id].l,key,idX,q[id].l);
}
Update(id);
}
}
int Merge(int idX,int idY){//both normal & special
if(idX==0 || idY==0) return idX+idY;
if(q[idX].val<=q[idY].val){
if(q[idX].rnd<=q[idY].rnd){
q[idX].r=Merge(q[idX].r,idY);
Update(idX);
return idX;
}
else{
q[idY].l=Merge(idX,q[idY].l);
Update(idY);
return idY;
}
}
else{
if(q[idX].rnd<=q[idY].rnd){
q[idY].r=Merge(idX,q[idY].r);
Update(idY);
return idY;
}
else{
q[idX].l=Merge(q[idX].l,idY);
Update(idX);
return idX;
}
}
}
int Get(int id){//for fa
if(fa[id]!=id) fa[id]=Get(fa[id]);
return fa[id];
}
public:
void Init(){
nw=0;
memset(root,0,sizeof(root));
memset(fa,0,sizeof(fa));//not a must
}
void Insert(int val,int k,int kind){//k == kind
Split(root[kind],val,rootX,rootY);
root[kind]=Merge(Merge(rootX,New(val,k)),rootY);
fa[k]=k;
}
void Build(int kindX,int kindY){
root[kindX]=root[kindY]=Merge(root[kindX],root[kindY]);
fa[Get(kindX)]=Get(kindY);
}
int Find(int id,int rank){
id=root[Get(id)];
while(1){
if(q[q[id].l].siz>=rank) id=q[id].l;
else if(q[q[id].l].siz+1==rank) return q[id].k!=0?q[id].k:-1;
else{
rank-=(q[q[id].l].siz+1);
id=q[id].r;
}
}
}
};
#undef N
fhqTreap q;
int n,m;
int main(){
freopen("input.in","r",stdin);
freopen("output.txt","w",stdout);
srand(time(0));
q.Init();
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=n;i++){
scanf("%d",&x);
q.Insert(x,i,i);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
q.Build(x,y);
}
scanf("%d",&m);
char tmpS[5];
while(m--){
scanf("%s%d%d",tmpS,&x,&y);
if(tmpS[0]=='Q'){
printf("%d\n",q.Find(x,y));
}
else{
q.Build(x,y);
}
}
return 0;
}
```
by 7k1danWhen @ 2022-03-29 22:03:32
两个freopen是我本地调试用的，请各位大佬忽略
by 7k1danWhen @ 2022-03-29 22:04:09