题解 P3224 【[HNOI2012]永无乡】

· · 题解

用并查集维护各个点的联通关系，用平衡树维护各个联通块的所有重要程度，连接两个联通块时启发式合并。

造轮子什么的最讨厌了，直接上pb_ds啊

虽然pb_ds是有join这个方法的，然而两棵树能合并的必要条件是合并的树中的所有元素都小于被合并的树中的所有元素，如 果不满足这个规则，那么合并的时候会抛出异常。

所以还需要手动把小树启发式合并到大树上。

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
//把这两个东西背下来
int Read()
{
    int x=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}

using namespace __gnu_pbds;
//把这个命名空间背下来
int imp[100005],fa[100005];
//重要程度，并查集
void init_set(int n)
{
    for(int i=1;i<=n;++i)
        fa[i]=i;
}

int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

void uni_set(int x,int y)
{
    x=find(x),y=find(y);
    fa[x]=y;
}

typedef tree<int,int,std::greater<int>,rb_tree_tag,
     tree_order_statistics_node_update> Tree;
Tree block[100005];
//每个点一棵红黑树，资瓷查询第k大
void init_tree(int n)
{
    for(int i=1;i<=n;++i)
        block[find(i)].insert(std::pair<int,int>(imp[i],i));
}//以重要度为关键字

void uni_tree(int x,int y)
{//启发式合并
    x=fa[x],y=fa[y];
    if(x==y)//如果已在同一联通块中，直接返回
        return;
    int size_x=block[x].size(),size_y=block[y].size();
    if(size_x>size_y)
        std::swap(x,y);//x更小
    Tree::point_iterator it=block[x].begin();
    for(;it!=block[x].end();++it)
    {
        block[y].insert(std::pair<int,int>(it->first,it->second));
        block[x].erase(it);
    }
    uni_set(x,y);
}

int main()
{
    int n=Read(),m=Read();
    init_set(n);
    for(int i=1;i<=n;++i)
        imp[i]=Read();
    for(int i=0;i<m;++i)
        uni_set(Read(),Read());
    init_tree(n);
    int q=Read();
    char opt[5];
    for(int i=0;i<q;++i)
    {
        scanf("%s",opt);
        if(opt[0]=='B')
            uni_tree(Read(),Read());
        else
        {
            int father=find(Read());
            int k=Read();
            if(k>block[father].size())
                puts("-1");
            else//注意，find_by_order找的是第k大，而且从0开始排
                printf("%d\n",block[father].find_by_order(block[father].size()-k)->second);
        }
    }
    return 0;
}