← 返回题目列表

Codeforces · 380/B

B. 塞雷贾和树

中文机器翻译题面 查看原题

Sereja 喜欢树木。今天他想出了一种革命性的新型二叉根树。

他的新树由n层组成,每个顶点由两个整数索引:层数和当前层上的顶点数。树根位于第 1 层,其索引为 (1, 1)。这是树构造的伪代码。

伪代码运行后,单元格cnt[level]包含级别level上的顶点数。单元格 left[level][position] 包含级别 level + 1 上的顶点编号,它是索引为(level,position)的顶点的左子节点,或者如果该顶点没有左子节点,则包含 -1。同样,单元格 right[level][position] 负责右子节点。您可以在注释中看到 n = 4 的树是什么样子。

Serja 喜欢把事情变得复杂,所以他首先制作了一棵树,然后为每个顶点添加一个空集 A(level,position)。然后Sereja执行m个操作。每个操作都是以下两种类型之一:

- 操作的格式为“1 t l r x”。对于所有顶点 level, position (level = t; l ≤ position ≤ r) 添加值 x 以设置 A(level, position)。
- 操作的格式为“2 t v”。对于顶点级别 position (level = t, position = v),找到顶点(level, position)子树中所有顶点集的并集。打印这些集合的并集的大小。

帮助 Sereja 执行操作。在这个问题中,集合只包含不同的值,如 C++ 中的 std::set。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 7000)。

接下来的 m 行包含操作的描述。第一种类型的运算由五个整数给出:1 t l r x (1 ≤ t ≤ n; 1 ≤ l ≤ r ≤ cnt[t]; 1 ≤ x ≤ 106)。第二种类型的运算由三个整数给出:2 t v (1 ≤ t ≤ n; 1 ≤ v ≤ cnt[t])。

输出

对于第二种类型的每个操作,将答案打印在一行上。

示例

输入 #1

4 5
1 4 4 7 1
1 3 1 2 2
2 1 1
2 4 1
2 3 3

输出 #1

2
0
1

注意

您可以通过以下链接找到使用根树时使用的定义:http://en.wikipedia.org/wiki/Tree_(graph_theory)

您可以在下面看到 n = 4 时构造的树的示例。