題目鏈接：http://poj.org/problem?id=2985
/**//*
題意：
給定N(N <= 200000)個操作，每個操作是以下兩種形式：
0 x y ： 合并x所在的組和y所在的組，如果x和y同組，不合并。
1 k：輸出第k大的組的元素個數(shù)。
解法：
樹狀數(shù)組 + 并查集
思路：
將元素的個數(shù)對應(yīng)樹狀數(shù)組的下標(biāo)，每次合并操作，在樹狀
數(shù)組中對應(yīng)兩個集合大小的位置分別減1，兩集合之后的位置+1，
詢問操作只需要二分答案，然后每次統(tǒng)計比k大的數(shù)的個數(shù)判可行
即可。
*/
#include <iostream>
using namespace std;
#define maxn 200010
int c[maxn];
int prev[maxn], num[maxn];
int n;
int lowbit(int x) 
{
return x & (-x);
}
void add(int pos, int num) {
while(pos <= n) {
c[pos] += num;
pos += lowbit(pos);
}
}
int sum(int pos) {
int s = 0;
while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
int find(int x) {
int q = x;
while(x != prev[x]) {
x = prev[x];
}
return x;
}
void Union(int x, int y) {
x = find(x);
y = find(y);
if(x != y) {
if(num[x] == num[y])
add(num[x], -2);
else {
add(num[x], -1);
add(num[y], -1);
}
add(num[x] + num[y], 1);
if(num[x] < num[y]) {
prev[x] = y;
num[y] += num[x];
}else {
prev[y] = x;
num[x] += num[y];
}
}
}
int Query(int k) {
int l = 1;
int r = n;
int ans = 0;
int all = sum(n);
while(l <= r) {
int m = (l + r) >> 1;
if(k <= all - sum(m-1)) {
l = m + 1;
ans = m;
}else
r = m - 1;
}
return ans;
}
int main() {
int i, m;
int op, x, y;
while(scanf("%d %d", &n, &m) != EOF) {
for(i = 1; i <= n; i++) {
c[i] = 0;
prev[i] = i;
num[i] = 1;
}
add(1, n);
while(m--) {
scanf("%d", &op);
if(op == 0) {
scanf("%d %d", &x, &y);
Union(x, y);
}else {
scanf("%d", &x);
printf("%d\n", Query(x));
}
}
}
return 0;
}