思路

平衡树+启发式合并

貌似也可以线段树合并

连边就是合并两个Treap，查询就是第k大

使用Treap，好写好调

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int Nodecnt=0,root[100100*2],fa[100100*2],n,m,w_p[100100*2];struct Node{    int lson,rson,sz,val,ran,num;}Treap[100100*2];int find(int x){    if(fa[x]==x)        return x;    else        return fa[x]=find(fa[x]);}queue
        
          q;void throwin(int x){    q.push(x);}int getnew(int val,int num){    int o;    if(q.size())        o=q.front(),q.pop();    else        o=++Nodecnt;    Treap[o].lson=Treap[o].rson=0;    Treap[o].sz=1;    Treap[o].ran=rand();    Treap[o].val=val;    Treap[o].num=num;    return o;}void pushup(int o){    Treap[o].sz=Treap[Treap[o].lson].sz+Treap[Treap[o].rson].sz+1;}void rorateL(int &o){    int x=Treap[o].rson;    Treap[o].rson=Treap[x].lson;    Treap[x].lson=o;    pushup(o);    pushup(x);    o=x;}void rorateR(int &o){    int x=Treap[o].lson;    Treap[o].lson=Treap[x].rson;    Treap[x].rson=o;    pushup(o);    pushup(x);    o=x;}void insert(int val,int num,int &o){    if(!o){        o=getnew(val,num);        return;    }    Treap[o].sz++;    if(val<=Treap[o].val){        insert(val,num,Treap[o].lson);        if(Treap[Treap[o].lson].ran
         
          Treap[Treap[o].lson].sz+1) return query(val-Treap[Treap[o].lson].sz-1,Treap[o].rson); else return query(val,Treap[o].lson);}void dfs(int &o,int to){ if(!o) return; insert(Treap[o].val,Treap[o].num,root[to]); dfs(Treap[o].lson,to); dfs(Treap[o].rson,to); throwin(o); o=0;}int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w_p[i]),fa[i]=i,insert(w_p[i],i,root[i]); for(int i=1;i<=m;i++){ int a,b; scanf("%d %d",&a,&b); if(find(a)!=find(b)){ if(Treap[find(a)].sz