P3224 [HNOI2012] 永无乡 · znzryb
## 题目大意
有 $n$ 座岛（编号 $1sim n$），每座岛有一个“重要度排名” $p_i$（是 $1\sim n$ 的一个排列，数值越小表示越重要）。初始有 m 座桥形成无向图，之后还会有 q 次操作：
- `B x y`：在岛 x 与 y 之间新建一座桥。
- `Q x k`：在当前与岛 x 连通的所有岛中，找出“重要度排名第 $k$ 小”的岛，输出该岛编号；若不存在则输出 $-1$。
## 思路讲解
[](https://www.notion.so/1154539447bd8057ab37c31c45b3a0c3) 这是此题的退化版（<10）
## AC代码
::: 源代码
```cpp
```
:::
## 心路历程（WA，TLE，MLE……）
40pts，TLE，不用平衡树stl的set合并太慢了。
::: 源代码
```cpp
//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
```
:::