[HNOI2012]永无乡

题意：一个点权图（不一定联通），两种操作

B x y 表示在岛 x 与岛 y 之间修建一座新桥。

Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。

算法见注释

#include<cstdio>
using namespace std;
const int N=5e6+6;

int n,m,tot;
int lc[N],rc[N],sz[N];
int rt[N];//每个元素的线段树的根节点编号

int p[N];//通过排名指向结点

void modify(int &u,int v,int l=1,int r=n){
    if(!u)u=++tot;
    if(l==r){sz[u]++;return;}
    int mid=(l+r)>>1;
    if(v<=mid)modify(lc[u],v,l,mid);
    else modify(rc[u],v,mid+1,r);
    sz[u]=sz[lc[u]]+sz[rc[u]];
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    lc[x]=merge(lc[x],lc[y]), rc[x]=merge(rc[x],rc[y]);
    return sz[x]=sz[lc[x]]+sz[rc[x]],x;
}
int kth(int u,int k,int l=1,int r=n){
    int mid=(l+r)>>1;
    if(l==r)return l;
    if(k<=sz[lc[u]])return kth(lc[u],k,l,mid);
    else return kth(rc[u],k-sz[lc[u]],mid+1,r);
}
namespace DIS{
    int f[N];
    void init(int k){for(int i=0;i<=k;i++)f[i]=i;}
    int gf(int k){return f[k]==k?k:f[k]=gf(f[k]);}
    void un(int u,int v){
        u=gf(u),v=gf(v);
        rt[v]=merge(rt[v],rt[u]);
        f[u]=v;
    }
    bool find(int u,int v){return gf(u)==gf(v);}
    int query(int u,int k){
        u=gf(u);
        if(sz[rt[u]]<k||k==0)return -1;
        return p[kth(rt[u],k)];
    }
}

int main(){
    scanf("%d%d",&n,&m);
    DIS::init(n);
    for(int i=1;i<=n;i++){
        rt[i]=++tot;//新建结点
        int x;
        scanf("%d",&x);
        p[x]=i;
        modify(rt[i],x);//添加一个元素x
    }
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(DIS::find(a,b))continue;
        DIS::un(a,b);
    }
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        char op[5];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='B'){
            if(DIS::find(a,b))continue;
            DIS::un(a,b);
        }
        else {
            printf("%d\n",DIS::query(a,b));
        }
    }
    return 0;
}
/*
 * 用并查集维护联通信息，每个联通块需要支持查询第k小
 * 维护联通块的权值线段树
 * 线段树合并
 */

[HNOI2012]永无乡

原文：https://www.cnblogs.com/sshwy/p/10989880.html