题目大意是这样的      查看原题

某人养了很多猫,从1-n编号,他想给她们(??!)分成几组,给出m个操作,其中可以

1)给出第i群猫和第j群猫,把她们合并。(注意猫i代表了第i群猫,而如果,猫k也在这群猫里,那猫k也能代表这群猫)

2)在线询问某次操作之后第k大的猫群有多大

考虑1)显然是一个并查集。

2)可以按照猫群大小建Fenwick Tree然后查找区间第k大数就可以了。

特别推荐这篇博文(虽然弱弱的我看了好久才看懂)

Press Here

然后是Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<utility>
#include<iterator>
using namespace std;

//fenwick tree -> fwt[i]维护猫的数目为i的猫团有几个 

int upat,fwt[270000]={0};
int fatherx[270000]={0},countx[270000]={0};
int cnum,opnum,cachea,cacheb,cachek,cacheop,ufsnum;

void readx(int& x)
{
	x=0; int k=1;
	register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int findx(int e)
{
	if (fatherx[e]!=e) fatherx[e]=findx(fatherx[e]);
	return fatherx[e];
}

void add(int pos,int val)
{
	while (pos<=upat)
	{
		fwt[pos]+=val;
		pos+=(pos&(-pos));
	}
}

int Kth_Small(int k)
{
	int pos=0;
	for (int i=18;i>=0;i--) if (pos+(1<<i)<=upat && fwt[pos+(1<<i)]<k) 
	{
		pos+=(1<<i);
		k-=fwt[pos];
	}
	return pos+1;
}

void mergex(int a,int b)
{
	int roota=findx(a),rootb=findx(b);
	if (roota!=rootb)
	{
		ufsnum--;
		add(countx[roota],-1);
		add(countx[rootb],-1);
		countx[roota]+=countx[rootb]; countx[rootb]=0;
		add(countx[roota],1);
		
		fatherx[rootb]=roota;
	}
}

int main()
{
	readx(cnum); readx(opnum);
	
	upat=cnum; ufsnum=cnum;
	for (int i=0;i<=cnum;i++) { fatherx[i]=i; countx[i]=1; }
	add(1,cnum);
	
	for (int o=1;o<=opnum;o++)
	{
		readx(cacheop);
		if (!cacheop)
		{
			readx(cachea); readx(cacheb);
			mergex(cachea,cacheb);
		}
		else
		{
			readx(cachek);
			printf("%d\n",Kth_Small(ufsnum-cachek+1));
		}
	}
	return 0;
}

 

分类:

发表评论

电子邮件地址不会被公开。 必填项已用*标注