#P10088. 大师兄的树

    ID: 9143 传统题 2000ms 512MiB 尝试: 3 已通过: 2 难度: 6 上传者: 标签>数据结构图论CF2100堆可持久化树形DP

大师兄的树

大师兄的树

题目描述

初始有 NN 棵互不相交的树,编号分别为 1,2,…,N1,2,\ldots,N。每棵树只有一个节点,节点 ii 的权值为 wiw_i。

接下来执行 QQ 次操作:

  1. 1 w x y:选择两棵当前独立的树,其根节点分别为 xx、yy。新建一个权值为 ww 的节点作为根,将树 xx、树 yy 分别接为它的左、右子树。若这是第 ii 次执行操作1,新节点的编号为 N+iN+i。操作后,xx、yy 不再是独立树的根。
  2. 2 x:删除当前某棵树的根节点 xx。它的左、右子树各自成为独立的树;若没有子树,则不产生新树。节点 xx 的权值随该节点一起删除,编号 xx 此后不能再使用。
  3. 3 x k:询问当前以 xx 为根的树中第 kk 大的节点权值。相同权值按节点个数重复计数。

保证所有操作合法:操作1中的 x,yx,y 是两棵不同的当前独立树的根;操作2和操作3中的 xx 是当前独立树的根;操作3中的 kk 不超过该树的节点数。不会引用未创建或已删除的节点。

所有查询的 kk 之和不超过 10N10N。

输入格式

第一行两个整数 N,QN,Q。

第二行 NN 个整数 w1,w2,…,wNw_1,w_2,\ldots,w_N。

接下来 QQ 行,每行一个操作,格式如上。

新建节点只按照操作1的次数编号,与总操作次数无关。节点一旦删除,编号不会再次分配。

输出格式

对于每次操作3,按照操作顺序输出一行一个整数,表示对应的第 kk 大权值。

若没有查询操作,则输出为空。

样例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

数据范围

  • 1≤N,Q≤1051\le N,Q\le 10^5。
  • 所有节点权值均为32位有符号整数,即 −231≤wi,w≤231−1-2^{31}\le w_i,w\le 2^{31}-1。
  • 对每次查询,1≤k≤1\le k\le 当前树的节点数,且所有查询的 kk 之和不超过 10N10N。
  • 保证所有操作满足题目描述中的合法性条件。

分为三个子任务,总分100分:

子任务 分值 额外限制
1 30 N,Q≤1000N,Q\le 1000
2 N,Q≤10000N,Q\le 10000
3 40 无额外限制