POJ 2985 The k-th Largest Group

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

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

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

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

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

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

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

Press Here

然后是Code