记录编号	593310	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	3.308 s
提交时间	2024-08-29 19:33:26	内存使用	28.99 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define debug() cout<<"I Love COGS\n"
int n,m,sum,idx;
struct node{
    int l,r,siz;
    int s[5];
}tr[MAXN*20];
int val[MAXN],f[MAXN],root[MAXN],siz[MAXN],num[MAXN];
void build(int l,int r,int now,int s){
    tr[now].l=l,tr[now].r=r,tr[now].siz=1;
//    cout<<now<<" "<<tr[now].l<<" "<<tr[now].r<<" "<<s<<endl;
    if(l>=r)return;
    int mid=(l+r)/2;
    if(s<=mid){
        tr[now].s[0]=++idx;
        build(l,mid,idx,s);
    }else{
        tr[now].s[1]=++idx;
        build(mid+1,r,idx,s);
    }
}
void pushup(int now){
    tr[now].siz=tr[tr[now].s[0]].siz+tr[tr[now].s[1]].siz;
}
int find(int now){
    if(f[now]==now)return now;
    else return f[now]=find(f[now]);
}
int ad(int p,int q){
    if(!p)return q;
    if(!q)return p;
//    cout<<p<<" "<<q<<" "<<tr[p].l<<" "<<tr[p].r<<" "<<tr[p].siz<<" "<<tr[q].siz<<endl; 
    tr[p].siz+=tr[q].siz;
    if(tr[p].l==tr[p].r){
//        tr[p].siz+=tr[q].siz;
        return p;
    }
    tr[p].s[0]=ad(tr[p].s[0],tr[q].s[0]);
    tr[p].s[1]=ad(tr[p].s[1],tr[q].s[1]);
//    pushup(p);
    return p; 
}
void ad_(int lz,int rz){
    if(siz[find(lz)]<siz[find(rz)])swap(lz,rz);
    ad(root[find(lz)],root[find(rz)]);
    siz[find(lz)]+=siz[find(rz)];
    f[find(rz)]=find(lz);
}
int re(int p,int k){
//    cout<<p<<" "<<tr[p].l<<" "<<tr[p].r<<" "<<tr[p].siz<<endl;
    if(tr[p].l==tr[p].r)return tr[p].l;
    if(tr[tr[p].s[0]].siz<k){
        k-=tr[tr[p].s[0]].siz;
        return re(tr[p].s[1],k);
    }else{
        return re(tr[p].s[0],k);
    }
}
int main(){
    freopen("bzoj_2733.in","r",stdin);
    freopen("bzoj_2733.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>val[i];
        num[val[i]]=i;
        siz[i]=1;
        root[i]=++idx;
        f[i]=i;
        build(1,n,idx,val[i]);
    }
    for(int i=1;i<=m;i++){
        int lz,rz;
        cin>>lz>>rz;
        ad_(lz,rz);
    }
//    debug();
    cin>>sum;
//    debug();
    for(int i=1;i<=sum;i++){
        char q1;
        int q2,q3;
//        debug();
        cin>>q1>>q2>>q3;
//        debug();
        if(q1=='Q'){
            if(siz[find(q2)]<q3)cout<<"-1\n";
            else cout<<num[re(root[find(q2)],q3)]<<endl;
        }else{
            ad_(q2,q3);
        }
    }
    return 0;
}