#P10088. 大师兄的树
大师兄的树
大师兄的树
题目描述
初始有 棵互不相交的树,编号分别为 。每棵树只有一个节点,节点 的权值为 。
接下来执行 次操作:
1 w x y:选择两棵当前独立的树,其根节点分别为 、。新建一个权值为 的节点作为根,将树 、树 分别接为它的左、右子树。若这是第 次执行操作1,新节点的编号为 。操作后,、 不再是独立树的根。2 x:删除当前某棵树的根节点 。它的左、右子树各自成为独立的树;若没有子树,则不产生新树。节点 的权值随该节点一起删除,编号 此后不能再使用。3 x k:询问当前以 为根的树中第 大的节点权值。相同权值按节点个数重复计数。
保证所有操作合法:操作1中的 是两棵不同的当前独立树的根;操作2和操作3中的 是当前独立树的根;操作3中的 不超过该树的节点数。不会引用未创建或已删除的节点。
所有查询的 之和不超过 。
输入格式
第一行两个整数 。
第二行 个整数 。
接下来 行,每行一个操作,格式如上。
新建节点只按照操作1的次数编号,与总操作次数无关。节点一旦删除,编号不会再次分配。
输出格式
对于每次操作3,按照操作顺序输出一行一个整数,表示对应的第 大权值。
若没有查询操作,则输出为空。
样例1
输入
2 3
5 7
1 1 1 2
2 3
3 1 1
输出
5
说明
新节点3的权值为1,左右子树分别是节点1和节点2。删除节点3后,节点1和节点2重新成为两棵独立的树。节点1的权值为5。
样例2
输入
4 11
5 -2 5 0
1 7 1 2
1 -3 3 4
1 5 5 6
3 7 1
3 7 4
2 7
3 5 2
2 5
3 2 1
1 9 1 6
3 8 3
输出
7
5
5
-2
5
数据范围
- 。
- 所有节点权值均为32位有符号整数,即 。
- 对每次查询, 当前树的节点数,且所有查询的 之和不超过 。
- 保证所有操作满足题目描述中的合法性条件。
分为三个子任务,总分100分:
| 子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 30 | |
| 2 | ||
| 3 | 40 | 无额外限制 |