洛谷P3224 永无乡 - 连通块合并查询第k小权值 并查集+线段树合并
题目链接：https://www.luogu.com.cn/problem/P3224
题目大意：
思路：直接给每个岛建立一棵线段树。然后用并查集合并岛，线段树合并一下两个岛的权值。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5+5;
int w[N], p[N], lc[N*20], rc[N*20], rt[N*20], id[N*20], tot=0, n, m;
vector<int> v[N];
int tre[N*20], ans[N];//节点信息
void Insert(int &i, int l, int r, int x, int Id){//建树
if(r<l) return;
i=++tot;//点
if(l==r){
id[i]=Id;
tre[i]++; return ;
}
int mid=(l+r)>>1;
if(x<=mid) Insert(lc[i], l, mid, x, Id);
if(x>mid) Insert(rc[i], mid+1, r, x, Id);
tre[i]=tre[lc[i]]+tre[rc[i]];//权值在区间[l, r]的元素个数
}
int Merge(int x, int y){//合并
if(!x) return y;
if(!y) return x;
lc[x]=Merge(lc[x], lc[y]);
rc[x]=Merge(rc[x], rc[y]);
tre[x]=tre[lc[x]]+tre[rc[x]];//节点信息合并
return x;
}
int query(int root, int l, int r, int x){//查询子树中权值<=x的节点个数
if(!root) return -1;
if(!x) return -1;
if(l==r){
if(tre[root]>=x){
return id[root];
}
return -1;
}
int mid=(l+r)>>1;
if(x>tre[lc[root]]) return query(rc[root], mid+1, r, x-tre[lc[root]]);
else return query(lc[root], l, mid, x);
}
int f[N];
int fd(int x){
if(f[x]==x) return x;
return f[x]=fd(f[x]);
}
int main(){
int x, y, q;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
scanf("%d", &w[i]);
f[i]=i;
}
for(int i=1; i<=n; i++){
Insert(rt[i], 1, n, w[i], i);
}
for(int i=1; i<=m; i++){
scanf("%d%d", &x, &y);
x=fd(x), y=fd(y); f[y]=x;
rt[x]=Merge(rt[x], rt[y]);
}
scanf("%d", &q);
while(q--){
char op[5];
scanf("%s%d%d", op, &x, &y);
x=fd(x);
if(op[0]=='B'){
y=fd(y);
if(x==y) continue;
f[y]=x;
rt[x]=Merge(rt[x], rt[y]);
//cout<<rt[x]<<" : "<<tre[rt[x]]<<endl;
}
else{
printf("%d\n", query(rt[x], 1, n, y));
}
}
return 0;
}
