```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN =1e5+5;
int root[MAXN];
int lson[MAXN<<5],rson[MAXN<<5],sum[MAXN<<5],cnt,id[MAXN];
inline void push_up(int p){sum[p]=sum[lson[p]]+sum[rson[p]];}
void insert(int& p,int l,int r,int x)
{
p=++cnt;
if(l==r)
{
sum[p]++;
return;
}
int mid=(l+r)>>1;
if(x<=mid) insert(lson[p],l,mid,x);
else insert(rson[p],mid+1,r,x);
push_up(p);
}
int query(int p,int l,int r,int k)
{
if(sum[p]<k) return -1;
if(l==r) return id[l];
int mid=(l+r)>>1;
if(sum[lson[p]]>=k) return query(lson[p],l,mid,k);
else return query(rson[p],mid+1,r,k-sum[lson[p]]);
}
int merge(int x,int y,int l,int r)
{
if(!x||!y) return x|y;
if(l==r) sum[x]+=sum[y];
int mid=(l+r)>>1;
lson[x]=merge(lson[x],lson[y],l,mid);
rson[x]=merge(rson[x],rson[y],mid+1,r);
push_up(x);
return x;
}
int fa[MAXN],n,m;
int find(int x){return fa[x]==x?x:find(fa[x]);}
inline int read()
{
int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+c-48;
return x*f;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
int x=read();
insert(root[i],1,n,x);
fa[i]=i;
id[x]=i;
}
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
u=find(u); v=find(v);
if(u==v) continue;
root[u]=merge(root[u],root[v],1,n);
fa[v]=u;
}
int q=read();
while(q--)
{
char op[3];
scanf("%s",op);
if(op[0]=='Q')
{
int x=read(),y=read();
x=find(x);
printf("%d\n",query(root[x],1,n,y));
}else
{
int x=read(),y=read();
x=find(x); y=find(y);
fa[y]=x;
root[x]=merge(root[x],root[y],1,n);
}
}
return 0;
}
```
by 404Not_Found @ 2021-12-28 13:21:18
在第二个操作的地方判断一下如果两个点在同一个联通块里面的情况。
by KAMIYA_KINA @ 2021-12-28 14:30:37
@[KAMIYA_KINA](/user/366935) 不是这个问题，并查集没路径压缩（我是sb），刚才发现，不过还是感谢。
by 404Not_Found @ 2021-12-29 12:42:40