来自FallDream的博客，未经允许，请勿转载，谢谢。
永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。 n≤100000,m≤n，q≤300000
这道题很容易看出来是平衡树+启发式合并
就是每一个联通块都维护一棵平衡树，然后建桥的时候如果两个点不在同一颗树，那么就把它们所在的平衡树合并。合并的时候选择把size较小的平衡树的点全部拿出来，插入到另一棵里面，可以证明这样的复杂度是最坏$O(nlog^{2}n)$的。
#include<iostream> #include<cstdio> #define MN 100000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int fa[MN+5],bel[MN+5],size[MN+5],c[MN+5][2],n,m,rt[MN+5],top,q[MN+5],s[MN+5]; inline void update(int x){size[x]=size[c[x][0]]+size[c[x][1]]+1;} void rotate(int x,int&k) { int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; if(y==k) k=x; else c[z][c[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; update(y);update(x); } void splay(int x,int&k) { for(;x!=k;rotate(x,k)) if(fa[x]!=k) rotate((c[fa[fa[x]]][1]==fa[x]^c[fa[x]][1]==x)?x:fa[x],k); } void ins(int&x,int k,int last) { if(!x){x=k;fa[x]=last;size[x]=1;c[x][0]=c[x][1]=0;return;} ins(c[x][s[k]>s[x]],k,x);++size[x]; } void dfs(int x) { if(c[x][0]) dfs(c[x][0]); q[++top]=x; if(c[x][1]) dfs(c[x][1]); } void Merge(int x,int y) { splay(x,rt[bel[x]]);splay(y,rt[bel[y]]); if(size[x]>size[y]) swap(x,y); top=0;dfs(x); for(int i=1;i<=top;i++) bel[q[i]]=bel[y],ins(rt[bel[y]],q[i],0),splay(q[i],rt[bel[y]]); } int find(int x,int rk) { int sz=size[c[x][0]]+1; if(sz==rk) return x; if(sz>rk) return find(c[x][0],rk); return find(c[x][1],rk-sz); } char op[5]; int main() { n=read();m=read(); for(int i=1;i<=n;i++)bel[i]=rt[i]=i,size[i]=1; for(int i=1;i<=n;i++)s[i]=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(); if(bel[x]!=bel[y]) Merge(x,y); } m=read(); for(int i=1;i<=m;i++) { scanf("%s",op+1);int x=read(),y=read(); if(op[1]=='Q') printf("%d ",size[rt[bel[x]]]<y?-1:find(rt[bel[x]],y)); else if(bel[x]!=bel[y]) Merge(x,y); } return 0; }