还有人类吗

题目描述

某天晚上，机房里正在进行一场 AtCoder Beginner Contest。

比赛开始后不久，一位 VJudge 标识末尾两字符经 Base64 编码后为 aHQ= 的选手，仿佛成功建立了通向题解空间的秘密信道，连续通过前六道题，排名一度冲到了 rk 40。

小 R 老师盯着排行榜沉默良久，终于忍不住对这位选手说了一句话：

感觉你已经不是人类了。

据说这位选手平日里极其擅长数据结构。为了检验他的数据结构能力究竟属于人类范畴，还是来自某种黑盒预言机的加密通信，小 R 老师决定拿出一道关于二叉搜索树的题。

一棵二叉搜索树是一棵有根二叉树，每个节点上有一个权值。对于任意节点 $x$，若它的权值为 $w_x$，则：

• $x$ 左子树内所有节点的权值都小于 $w_x$；
• $x$ 右子树内所有节点的权值都大于 $w_x$。

我们用如下过程描述在一棵 BST 中查找权值 $a$：

void find(x, a) {
    if (x == 0 || w[x] == a) return;
    if (w[x] > a) find(l[x], a);
    else find(r[x], a);
}

其中 $x=0$ 表示空节点，$l[x]$ 和 $r[x]$ 分别表示 $x$ 的左儿子和右儿子。

定义 $A(root,a)$ 为执行 find(root, a) 时访问到的所有非空节点组成的序列。

定义这次查找的代价为：

$$\sum_{v\in A(root,a)} w_v$$

现在有 $n$ 棵初始为空的 BST，编号为 $1,2,\ldots,n$。

接下来有 $m$ 次操作，操作分为两种：

• 1 l r w：对于所有 $i\in[l,r]$，将整数 $w$ 插入第 $i$ 棵 BST 中。插入从根开始，按照和 find(root, w) 相同的方式向下走；如果走到空节点，则在该位置新建一个权值为 $w$ 的节点。
• 2 x a：求在第 $x$ 棵 BST 中查找 $a$ 的代价。

题目保证所有第一类操作中的 $w$ 两两不同。

输入格式

第一行包含两个整数 $n,m$，分别表示 BST 的数量和操作次数。

接下来 $m$ 行，每行描述一次操作，格式为以下两种之一：

1 l r w

或

2 x a

含义如题目描述所示。

输出格式

对于每个第二类操作，输出一行一个整数，表示对应查找的代价。

样例输入

3 9
1 1 2 2
1 1 3 1
1 2 3 3
2 1 2
2 1 4
2 2 2
2 2 4
2 3 2
2 3 4

样例输出

2
2
2
5
4
4

样例解释

前三次操作后：

第 $1$ 棵 BST 中依次插入了 $2,1$，其结构为：

  2
 /
1

因此查找 $2$ 的代价为 $2$，查找 $4$ 时只访问节点 $2$，代价也为 $2$。

第 $2$ 棵 BST 中依次插入了 $2,1,3$，其结构为：

  2
 / \
1   3

因此查找 $2$ 的代价为 $2$，查找 $4$ 时访问节点 $2,3$，代价为：

$$2+3=5$$

第 $3$ 棵 BST 中依次插入了 $1,3$，其结构为：

1
 \
  3

因此查找 $2$ 和 $4$ 时都会访问节点 $1,3$，代价均为：

$$1+3=4$$

样例 2

见选手目录下的 human/human2.in 与 human/human2.ans。

该样例满足测试点 $1\sim 4$ 的约束条件。

样例 3

见选手目录下的 human/human3.in 与 human/human3.ans。

该样例满足测试点 $5\sim 8$ 的约束条件。

样例 4

见选手目录下的 human/human4.in 与 human/human4.ans。

该样例满足测试点 $9\sim 13$ 的约束条件。

样例 5

见选手目录下的 human/human5.in 与 human/human5.ans。

该样例满足测试点 $14\sim 22$ 的约束条件。

样例 6

见选手目录下的 human/human6.in 与 human/human6.ans。

该样例满足测试点 $23\sim 29$ 的约束条件。

样例 7

见选手目录下的 human/human7.in 与 human/human7.ans。

该样例满足测试点 $30\sim 36$ 的约束条件。

样例 8

见选手目录下的 human/human8.in 与 human/human8.ans。

该样例满足测试点 $37\sim 50$ 的约束条件。

数据范围

对于所有测试数据，均满足：

• $1\le n,m\le 2\times 10^5$；
• 对于第一类操作，$1\le l\le r\le n$，$1\le w\le 10^9$；
• 对于第二类操作，$1\le x\le n$，$1\le a\le 10^9$；
• 所有第一类操作中的 $w$ 两两不同。

记 $K$ 为第一类操作的数量。

本题共 $50$ 个测试点，每个测试点 $2$ 分。

测试点编号	分值	约束条件
$1\sim 4$	$8$	$n,m\le 300$
$5\sim 8$		对所有第一类操作，均有 $l=1,r=n$，且 $m\le 5000$
$9\sim 13$	$10$	第一类操作中的 $w$ 按操作时间严格递增，且对每个第二类操作，$a$ 不小于此前所有第一类操作中的最大 $w$
$14\sim 22$	$18$	第一类操作中的 $w$ 按操作时间严格递增
$23\sim 29$	$14$	$K\le 500$
$30\sim 36$		每次查找访问到的非空节点数量不超过 $50$
$37\sim 50$	$28$	无额外限制