POJ2985 The K-th Lagest Group

どう見てもデータ構造ゲー。とりあえずグループにするということでUnion-findをつくる。
BITでもつかって「n匹以下が属するグループ数」の累積和をもっといてやると通る。
オーダーはO(m log^2 n)。

#include<stdio.h>
#include<vector>
#include<algorithm>
int par[200000];
int ran[200000];
int ren[200000];
void init()
{
	for(int i=0;i<200000;i++)
	{
		par[i]=i;
		ran[i]=0;
		ren[i]=1;
	}
}
int find(int a)
{
	if(par[a]==a)
	{
		return a;
	}
	else
	{
		return par[a]=find(par[a]);
	}
}
void unite(int a,int b)
{
	a=find(a);
	b=find(b);
	if(a==b)
	{
		return;
	}
	if(ran[a]>ran[b])
	{
		par[b]=a;
		ren[a]+=ren[b];
	}
	else
	{
		par[a]=b;
		ren[b]+=ren[a];
	}
	if(ran[a]==ran[b])
	{
		ran[b]++;
	}
}
int bit[262145];
void init2()
{
	for(int i=0;i<262144;i++)
	{
		bit[i]=0;
	}
}
void add(int a,int b)
{
	for(;;)
	{
		bit[a]+=b;
		a+=a&-a;
		if(a>200001)
		{
			break;
		}
	}
}
int sum(int a)
{
	int gou=0;
	for(;;)
	{
		gou+=bit[a];
		a-=a&-a;
		if(a==0)
		{
			break;
		}
	}
	return gou;
}
int main()
{
	int cat,query;
	scanf("%d%d",&cat,&query);
	init();
	init2();
	add(1,cat);
	int gro=cat;
	for(int i=0;i<query;i++)
	{
		int whi;
		scanf("%d",&whi);
		if(whi==0)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			a--;
			b--;
			a=find(a);
			b=find(b);
			if(find(a)!=find(b))
			{
				add(ren[a],-1);
				add(ren[b],-1);
				add(ren[a]+ren[b],1);
				unite(a,b);
				gro--;
			}
		}
		else
		{
			int ban;
			scanf("%d",&ban);
			int beg=1,end=cat;
			int mok=gro-ban+1;
			for(;;)
			{
				int med=(beg+end)/2;
				if(sum(med)<mok)
				{
					beg=med+1;
				}
				else
				{
					end=med;
				}
				if(beg==end)
				{
					printf("%d\n",beg);
					break;
				}
			}
		}
	}
}