题目链接:http://poj.org/problem?id=2985
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
题意:
给定N(N <= 200000)个操作,每个操作是以下两种形式:
0 x y : 合并x所在的组和y所在的组,如果x和y同组,不合并。
1 k:输出第k大的组的元素个数。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
解法:
树状数组 + 并查集
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
将元素的个数对应树状数组的下标,每次合并操作,在树状
数组中对应两个集合大小的位置分别减1,两集合之后的位置+1,
询问操作只需要二分答案,然后每次统计比k大的数的个数判可行
即可。
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define maxn 200010
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int c[maxn];
int prev[maxn], num[maxn];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int lowbit(int x)
{
return x & (-x);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void add(int pos, int num)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(pos <= n)
{
c[pos] += num;
pos += lowbit(pos);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int sum(int pos)
{
int s = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(pos > 0)
{
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int find(int x)
{
int q = x;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(x != prev[x])
{
x = prev[x];
}
return x;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Union(int x, int y)
{
x = find(x);
y = find(y);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(x != y)
{
if(num[x] == num[y])
add(num[x], -2);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
add(num[x], -1);
add(num[y], -1);
}
add(num[x] + num[y], 1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(num[x] < num[y])
{
prev[x] = y;
num[y] += num[x];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
prev[y] = x;
num[x] += num[y];
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int Query(int k)
{
int l = 1;
int r = n;
int ans = 0;
int all = sum(n);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(l <= r)
{
int m = (l + r) >> 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(k <= all - sum(m-1))
{
l = m + 1;
ans = m;
}else
r = m - 1;
}
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i, m;
int op, x, y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(scanf("%d %d", &n, &m) != EOF)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= n; i++)
{
c[i] = 0;
prev[i] = i;
num[i] = 1;
}
add(1, n);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(m--)
{
scanf("%d", &op);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(op == 0)
{
scanf("%d %d", &x, &y);
Union(x, y);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
scanf("%d", &x);
printf("%d\n", Query(x));
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return 0;
}