← 返回题目列表

Codeforces · 960/D

D. 完整二叉树查询

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

您有一个具有无限级别的完整二叉树。

每个节点都有一个初始值。如果节点的值为 x,则其左子节点的值为 2·x,右子节点的值为 2·x + 1。

根的值为 1。

您需要回答Q问题。

有 3 种类型的查询:

1.将与值为X的节点同级的所有节点的值循环平移K个单位。 (任何其他级别的值/节点不受影响)。
2.将与值为X的节点同级的节点循环移位K个单位。 (这些节点的子树将随之移动)。
3. 打印从值为 X 的节点到根的简单路径上遇到的每个节点的值。

正 K 表示右循环移位,负 K 表示左循环移位。

保证至少存在一个类型 3 查询。

输入

第一行包含一个整数 Q (1 ≤ Q ≤ 105)。

然后是 Q 查询,每行一个:

- 类型 1 和 2 的查询具有以下格式:T X K (1 ≤ T ≤ 2; 1 ≤ X ≤ 1018; 0 ≤ |K| ≤ 1018),其中 T 是查询的类型。
- 类型 3 的查询具有以下格式:3 X (1 ≤ X ≤ 1018)。

输出

对于类型 3 的每个查询,按降序打印遇到的所有节点的值。

示例

输入 #1

5
3 12
1 2 1
3 12
2 4 -1
3 8

输出 #1

12 6 3 1
12 6 2 1
8 4 2 1

输入 #2

5
3 14
1 5 -3
3 14
1 3 1
3 14

输出 #2

14 7 3 1
14 6 3 1
14 6 2 1

注意

以下是第一个测试用例中树的前 4 层的图像:

原文:

查询1 2 1后:

查询2 4 -1后: