并查集 + 树状数组求第k大
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int const MAXN = 200010;
int n,m;
int c[MAXN],father[MAXN],cnt[MAXN];
void Init(){
for(int i = 1;i < MAXN;i++){
father[i] = i;
cnt[i] = 1;
}
memset(c,0,sizeof(c));
}
int Find(int x){
int y = x;
while(y != father[y]){
y = father[y];
}
while(x != father[x]){
int temp = x;
x = father[x];
father[temp] = y;
}
return x;
}
int LowBit(int x){
return x & (-x);
}
void Add(int x,int d){
while(x < MAXN){
c[x] += d;
x += LowBit(x);
}
}
int Sum(int x){
int ret = 0;
while(x > 0){
ret += c[x];
x -= LowBit(x);
}
return ret;
}
int main(){
while(~scanf("%d%d",&n,&m)){
Init();
Add(1,n);
int num = n;
for(int i = 1;i <= m;i++){
int a;
scanf("%d",&a);
if(a){
int k;
scanf("%d",&k);
k = num - k + 1;
int l = 1,r = n;
while(l <= r){
int mid = (l + r) >> 1;
if(Sum(mid) >= k) r = mid - 1;
else l = mid + 1;
}
printf("%d\n",l);
}
else{
int x,y;
scanf("%d%d",&x,&y);
int xx = Find(x);
int yy = Find(y);
if(xx == yy) continue;
Add(cnt[xx],-1);
Add(cnt[yy],-1);
cnt[xx] += cnt[yy];
Add(cnt[xx],1);
father[yy] = xx;
num--;
}
}
}
return 0;
}