P3224 [HNOI2012] 永无乡

题目大意

有 $n$ 座岛（编号 $1sim n$），每座岛有一个“重要度排名” $p_i$（是 $1\sim n$ 的一个排列，数值越小表示越重要）。初始有 m 座桥形成无向图，之后还会有 q 次操作：

• B x y：在岛 x 与 y 之间新建一座桥。

• Q x k：在当前与岛 x 连通的所有岛中，找出“重要度排名第 $k$ 小”的岛，输出该岛编号；若不存在则输出 $-1$。

思路讲解

这是此题的退化版（<10）

AC代码

源代码

心路历程（WA，TLE，MLE……）

40pts，TLE，不用平衡树stl的set合并太慢了。

源代码

//https://www.luogu.com.cn/problem/P3224
#include <iostream>
#include <vector>
#include <set>
#include <iterator>
using namespace std;
const int maxn=1e5+10;
int n,q,u,v,k,m,fa[maxn],p[maxn];  // fa is disjointed set to upd connected components
char op;
struct cmp{
    bool operator()(int a,int b){
        if(a!=b) return p[a]<p[b];
    }
};
set <int,cmp > g[maxn];
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]); // compress path
        return fa[x];
    }else{
        return x;
    }
}
void unionn(int i,int j){
    int i_fa=find(i);
    int j_fa=find(j);
    fa[j_fa]=i_fa;
    g[i_fa].insert(g[j_fa].begin(),g[j_fa].end());
    g[j_fa].clear();	
}
inline void query1(){
    unionn(u,v);
}
inline void query2(){
    int v_fa=find(v),cnt=0;
    set<int>::iterator it=g[v_fa].begin();
    if(g[v_fa].size()<k){
        cout<<-1<<endl;return;
    }
    advance(it,k-1);
    cout<<*it<<endl;	
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    for(int i=1;i<=n;i++) fa[i]=i,g[i].insert(i);  //initialize disjointed set.
    for(int _=1;_<=m;_++){
        cin>>u>>v;query1();
    }
    cin>>q;
    for(int _=1;_<=q;_++){
        cin>>op;
        if(op=='B')
            cin>>u>>v,query1();
        else
            cin>>v>>k,query2();
    }
    cin>>n;
}
// 40pts https://www.luogu.com.cn/record/179949072