题目链接：http://poj.org/problem?id=2985
/**//*
题意：
给定N(N <= 200000)个操作，每个操作是以下两种形式：
0 x y ： 合并x所在的组和y所在的组，如果x和y同组，不合并。
1 k：输出第k大的组的元素个数。
解法：
树状数组 + 并查集
思路：
将元素的个数对应树状数组的下标，每次合并操作，在树状
数组中对应两个集合大小的位置分别减1，两集合之后的位置+1，
询问操作只需要二分答案，然后每次统计比k大的数的个数判可行
即可。
*/
#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;
}