并查集、整体二分、线段树合并

Solution 1：考虑使用树形结构描述合并过程，最开始每个岛屿都是一棵独立的树，每次有效合并会将两棵树合并为一棵树。新建一个节点，把两棵树的树根接在这个节点下面得到一棵新的树。

现在询问被转化为求出有根树森林中一个节点子树内的所有叶子中权值第 $k$ 小的是哪个节点，把叶子节点转成序列后整体二分。

由于 $n,m$ 同阶，时间复杂度 $O(q \log ^2 n)$。

#include<bits/stdc++.h>
using namespace std;
struct Query{int x,k,i;Query(int _x,int y,int z):x(_x),k(y),i(z){}};
int f[200'005],w[200'005],le[200'005],ri[200'005],son[200'005][2];
int n,m,q,cnt,pos,a[100'005],c[100'005],ex[100'005],ans[300'005];
pair<int,int> p[100'005];
int ask(int x){return x==f[x] ? x:f[x]=ask(f[x]);}
void connect(int x,int y){
    x=ask(x),y=ask(y);
    if(x==y) return;
    ++cnt,f[cnt]=cnt,f[x]=cnt,f[y]=cnt;
    w[cnt]=w[x]+w[y];
    son[cnt][0]=x,son[cnt][1]=y;
}
void dfs(int x){
    if(x<=n){
        ++pos,le[x]=pos,ri[x]=pos;
        p[x]=make_pair(a[x],pos);
    }
    else{
        dfs(son[x][0]),dfs(son[x][1]);
        le[x]=le[son[x][0]];
        ri[x]=ri[son[x][1]];
    }
}
void add(int x,int y){while(x<=n) c[x]+=y,x+=x&-x;}
int sum(int x){int ret=0;while(x) ret+=c[x],x-=x&-x;return ret;}
void overall_binary(vector<Query> v,int l,int r){
    if(l==r){
        for(auto i:v) ans[i.i]=ex[l];
        return;
    }
    int mid=(l+r)>>1;
    while(pos+1<=n&&p[pos+1].first<=mid) ++pos,add(p[pos].second,1);
    while(pos>=1&&p[pos].first>mid) add(p[pos].second,-1),--pos;
    vector<Query> lv,rv;
    for(auto i:v){
        if(sum(ri[i.x])-sum(le[i.x]-1)>=i.k) lv.push_back(i);
        else rv.push_back(i);
    }
    overall_binary(lv,l,mid),overall_binary(rv,mid+1,r);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m,cnt=n;
    for(int i=1;i<=n;i++) cin>>a[i],f[i]=i,w[i]=1,ex[a[i]]=i;
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y,connect(x,y);
    }
    vector<Query> v;
    cin>>q;
    for(int i=1;i<=q;i++){
        static char opt;
        static int x,y;
        cin>>opt>>x>>y;
        if(opt=='B') connect(x,y);
        else if(w[ask(x)]<y) ans[i]=-1;
        else v.push_back(Query(ask(x),y,i));
    }
    for(int i=1;i<=cnt;i++) if(ask(i)==i) dfs(i);
    pos=0,sort(p+1,p+n+1);
    overall_binary(v,1,n);
    for(int i=1;i<=q;i++) if(ans[i]!=0) cout<<ans[i]<<'\n';
    return 0;
}

Solution 2：线段树合并维护每个联通块信息，查询时在线段树上二分。

由于 $n,m$ 同阶，时间复杂度 $O(q \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int w,ls,rs;}s[100'005*18];
int n,m,q,seg,f[100'005],w[100'005],ex[100'005],ro[100'005];
void update(int &u,int l,int r,int p){
    if(u==0) u=++seg;
    if(l==r) return ++s[u].w,void();
    int mid=(l+r)>>1;
    if(p<=mid) update(s[u].ls,l,mid,p);
    else update(s[u].rs,mid+1,r,p);
    s[u].w=s[s[u].ls].w+s[s[u].rs].w;
}
int merge(int x,int y,int l,int r){
    if(x==0||y==0) return x+y;
    if(l==r) return s[x].w+=s[y].w,x;
    int mid=(l+r)>>1;
    s[x].ls=merge(s[x].ls,s[y].ls,l,mid);
    s[x].rs=merge(s[x].rs,s[y].rs,mid+1,r);
    s[x].w=s[s[x].ls].w+s[s[x].rs].w;
    return x;
}
int frank(int u,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(s[s[u].ls].w>=k) return frank(s[u].ls,l,mid,k);
    return frank(s[u].rs,mid+1,r,k-s[s[u].ls].w);
}
int ask(int x){return x==f[x] ? x:f[x]=ask(f[x]);}
void connect(int x,int y){
    x=ask(x),y=ask(y);
    if(x==y) return;
    f[x]=y,w[y]+=w[x];
    ro[y]=merge(ro[x],ro[y],1,n);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        static int x;
        cin>>x,ex[x]=i;
        w[i]=1,f[i]=i;
        update(ro[i],1,n,x);
    }
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y,connect(x,y);
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        static char opt;
        static int x,y;
        cin>>opt>>x>>y;
        if(opt=='B') connect(x,y);
        else if(w[ask(x)]<y) cout<<"-1"<<'\n';
        else cout<<ex[frank(ro[ask(x)],1,n,y)]<<'\n';
    }
    return 0;
}