P3224 [HNOI2012] 永无乡 题解

· · 题解

挑战最短代码(仅仅 50 行)，vector大法好。

大致题意

求任意联通块第 k 大的点，并要求支持连通块合并。

核心思路

暴力地维护 n 颗平衡树，t_i 表示以 i 为根的连通块所构成的平衡树。

合并就直接将小一点的平衡树上的所有元素加入到另一颗上。

可以注意到，均摊之下每个点只会被合并 \log n 次。

这就是此题的基本做法。

但是，本题解还没还有结束。

为了缩小码量，可以使用一种新科技——vector平衡树。

平衡树代码

插入操作找第一个大于等于 key 的位置，然后在这个位置插入 key 。

void insert(int key,int id){
    auto it = lower_bound(t[id].begin(),t[id].end(),key);
    t[id].insert(it,key);
}

查询操作更加简单，直接输出即可。

输出之前判断一下平衡树大小，来检查是否有第 k 大的元素。

int query(int key,int id){
    if(key > t[id].size())return -1;
    return q[t[id][key-1]];
}

AC 代码

#include<bits/stdc++.h>
using namespace std;
int p[100010],q[100010];
int n,m;
int f[100010];
vector<int> t[100010];
int find(int x){
    return (f[x] == x?x:f[x] = find(f[x]));
}
void hb(int u,int v){
    f[find(u)] = find(v);
}
void insert(int key,int id){
    auto it = lower_bound(t[id].begin(),t[id].end(),key);
    t[id].insert(it,key);
}
int query(int key,int id){
    if(key > t[id].size())return -1;
    return q[t[id][key-1]];
}
void join(int u,int v){
    int fu = find(u),fv = find(v);
    if(t[fu].size()>t[fv].size())swap(u,v);
    fu = find(u),fv = find(v);
    for(int v:t[fu])insert(v,fv);
    t[fu].clear();
    hb(u,v);
}
int u,v;
int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        cin>>p[i];
        q[p[i]] = i;
        f[i] = i;
        insert(p[i],i);
    }
    for(int i = 1;i <= m;i++){
        cin>>u>>v;
        if(find(u)!=find(v))join(u,v);
    }
    int q;
    cin>>q;
    while(q--){
        char c;
        cin>>c>>u>>v;
        if(c == 'Q')cout<<query(v,find(u))<<endl;
        else if(find(u) != find(v))join(u,v);
    }
    return 0;
}