好久没写Splay了，写一下练手
看到查询第 k 大肯定想到权值线段树平衡树
所以直接上 Splay ，用并查集维护联通
合并直接启发式合并就好了
启发式合并就是把节点少的平衡树每个点都拆下来，一个个插到另一个树上..
查询第k大只要知道第 k 大的值，就知道编号了，因为每个值都唯一对应一个编号
注意细节就好了
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> 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<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7,INF=1e9+7; int n,cnt,m,Q; int ch[N][2],fa[N],sz[N],val[N],rt[N],mp[N]; int f[N]; inline int find(int x) { return x==f[x] ? x : f[x]=find(f[x]); } inline void pushup(int &x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; } inline void rotate(int x,int &k) { int y=fa[x],z=fa[y],d=(ch[y][1]==x); if(y!=k) ch[z][(ch[z][1]==y)]=x; else k=x; fa[x]=z; fa[y]=x; fa[ch[x][d^1]]=y; ch[y][d]=ch[x][d^1]; ch[x][d^1]=y; pushup(y); pushup(x); } inline void splay(int x,int &k) { while(x!=k) { int y=fa[x],z=fa[y]; if(y!=k) { if( (ch[z][1]==y) ^ (ch[y][1]==x) ) rotate(x,k); else rotate(y,k); } rotate(x,k); } } inline int Q_th(int x,int k)//在x的Splay里查询第k大 { int now=rt[x]; while(233) { if(ch[now][0]&&k<=sz[ch[now][0]]) { now=ch[now][0]; continue; } if(ch[now][1]&&k>sz[ch[now][0]]+1) { k-=sz[ch[now][0]]+1; now=ch[now][1]; continue; } return val[now]; } } inline void ins(int x,int v)//插入值v到x的Splay里 { int now=rt[x],pre=0; while(now) { pre=now; now=ch[now][ v>val[now] ]; } now=++cnt; if(pre) ch[pre][ v>val[pre] ]=now; sz[now]=1; val[now]=v; fa[now]=pre; pushup(now); splay(now,rt[x]); } void dfs(int x,int y)//dfs合并Splay { if(ch[x][0]) dfs(ch[x][0],y); if(ch[x][1]) dfs(ch[x][1],y); ins(y,val[x]); } inline void merge(int x,int y)//处理合并指令 { int xa=find(x),ya=find(y); if(xa==ya) return;//同一颗树上不需要合并 f[xa]=ya; if(sz[rt[xa]]>sz[rt[ya]]) swap(xa,ya); dfs(rt[xa],ya); } int main() { int a,b; char c[5]; n=read(); m=read(); cnt=n; for(int i=1;i<=n;i++) { val[i]=read(); mp[val[i]]=i; rt[i]=i; sz[i]=1; f[i]=i; } for(int i=1;i<=m;i++) { a=read(),b=read(); merge(a,b); } Q=read(); for(int i=1;i<=Q;i++) { scanf("%s",c); a=read(); b=read(); if(c[0]=='Q') printf("%d ",sz[rt[find(a)]]>=b ? mp[Q_th(find(a),b)] : -1); else merge(a,b); } return 0; }