CSL的可并堆

发布时间: 2018年6月14日 17:53   最后更新: 2018年6月14日 19:43   时间限制: 2000ms   内存限制: 256M

CSL在上数据结构课的时候,遇到了一个问题:怎么高效地合并两个堆?这可难倒他了。

他至今不会实现这样的数据结构,但是他希望你帮帮他完成以下两件事:

  • 0 x y:合并$x$和$y$所在的堆。(如果本来就在一个堆,就不用合并)
  • 1 k:查询第$k$多的堆中的结点个数。

一共有$n$个结点,编号为$1 \sim n$。起初每个结点自己是一个堆。

第一行有一个整数$T$,表示测试数据的组数。
对于每组测试数据,第一行有两个整数$n, m$,表示结点的个数和操作的个数。
接下来$m$行,每行输入0 x y或者1 k描述一个操作,如题目所述。
$T \le 5$
$1 \le n, m \le 10 ^ 5$
$1 \le x, y \le n$

对于每组测试数据中$1$的操作,输出结点的个数。

复制
1
5 4
0 1 2
1 2
0 3 4
1 2
1
2

最开始有$5$堆:$1,1,1,1,1$;第一次操作后变成$2,1,1,1$;第二次操作后变成$2,2,1$。

data structure

ACM集训队暑期集训热身赛