初始给定一个n个点m条边的无向图，q次操作，每次要么新增一条边，要么查询与某个点相连的所有点里点权第K小的点的编号。
查询联通分量容易想到并查集，查询第K大需要用平衡树，容易想到每个联通分量维护一棵平衡树，
每次新增加一条边对联通分量的影响就是合并两颗平衡树，为了保障复杂度正确，我们采用启发式合并，每次把小的联通分量的每个值暴力插到大的联通分量中，
简单来看，启发式合并一次，容量至少对小的联通分量来说是翻倍，再加上插入平衡树的均摊复杂度是O（logn）的，乍一看复杂度是O（nlog^2n）的
（不过camp讲课的时候说，把小的Splay的每个数值从小到大插入到大的Splay中，时间复杂度是O（nlogn）的，证明需要用到Dynamic Finger Theorem）
然后，貌似就做完了
#include<bits/stdc++.h> using namespace std; const int maxn=5e5; const int INF=0x3f3f3f3f; typedef long long ll; struct Splay { int ch[2]; int fa; int cnt,val,sz; }b[maxn+5]; int father[maxn+5]; int tot=0,root[maxn+5]; inline int newNode(int fa,int val) { int p=++tot; b[p].fa=fa; b[p].val=val; b[p].cnt=b[p].sz=1; if (fa) b[fa].ch[b[fa].val<val]=p; b[p].ch[0]=b[p].ch[1]=0; return p; } inline int checkR(int p) { return b[b[p].fa].ch[1]==p; } inline void pushup(int p) { b[p].sz=b[p].cnt; if (b[p].ch[0]) b[p].sz+=b[b[p].ch[0]].sz; if (b[p].ch[1]) b[p].sz+=b[b[p].ch[1]].sz; } inline void RotateNode(int p) { int f=b[p].fa,ff=b[f].fa,w=checkR(p); b[f].ch[w]=b[p].ch[w^1]; b[b[f].ch[w]].fa=f; b[f].fa=p; b[p].ch[w^1]=f; b[p].fa=ff; if (ff) b[ff].ch[b[ff].ch[1]==f]=p; pushup(f); pushup(p); } inline void SplayNode(int p,int goal,int q) //把p旋转为goal的儿子 { while (b[p].fa!=goal) { int f=b[p].fa; int ff=b[f].fa; if (ff!=goal) { if (checkR(p)==checkR(f)) RotateNode(f); else RotateNode(p); } RotateNode(p); } if (goal==0) root[q]=p; } inline void InsertNode(int val,int q) { int u=root[q],fa=0; while (u) { if (b[u].val==val) { b[u].cnt++; pushup(u); SplayNode(u,0,q); return ; } fa=u; u=b[u].ch[b[u].val<val]; } u=newNode(fa,val); SplayNode(u,0,q); } inline int getVal(int rk,int q) { int u=root[q]; while (u) { if (rk<=b[b[u].ch[0]].sz) u=b[u].ch[0]; else if (rk<=b[b[u].ch[0]].sz+b[u].cnt) { SplayNode(u,0,q); break; } else { rk-=(b[b[u].ch[0]].sz+b[u].cnt); u=b[u].ch[1]; } } return b[u].val; } int _find(int x) { if (x==father[x]) return x; father[x]=_find(father[x]); return father[x]; } void dfs(int p,int to) { if (b[p].ch[0]) dfs(b[p].ch[0],to); InsertNode(b[p].val,to); if (b[p].ch[1]) dfs(b[p].ch[1],to); } void dfsSplay(int u) { printf("%d ",b[u].val); if (b[u].ch[0]) dfsSplay(b[u].ch[0]); if (b[u].ch[1]) dfsSplay(b[u].ch[1]); } void _merge(int u,int v) { u=_find(u); v=_find(v); if (u==v) return ; if (b[root[u]].sz>b[root[v]].sz) swap(u,v); father[u]=v; dfs(root[u],v); } char s[10]; int n,m,q,x,y; int a[maxn+5],mp[maxn+5]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) father[i]=i; for (int i=1;i<=n;i++) { scanf("%d",&a[i]); mp[a[i]]=i; } for (int i=1;i<=n;i++) InsertNode(a[i],i); //for (int i=1;i<=n;i++) printf("%d %d %d ",i,root[i],b[root[i]].val); while (m--) { scanf("%d%d",&x,&y); _merge(x,y); } scanf("%d",&q); while (q--) { scanf("%s",s); scanf("%d%d",&x,&y); if (s[0]=='B') { _merge(x,y); } else { int u=_find(x); if (b[root[u]].sz<y) printf("-1 "); else printf("%d ",mp[getVal(y,u)]); } } return 0; }