CF960D Full Binary Tree Queries
题目描述
你有一棵具有无限层数的满二叉树。
每个节点都有一个初始值。如果某个节点的值为 $x$，那么它的左孩子的值为 $2x$，右孩子的值为 $2x+1$。
根节点的值为 $1$。
你需要回答 $Q$ 个询问。
共有 $3$ 种类型的询问：
1. 将与值为 $X$ 的节点处于同一层的所有节点的值循环平移 $K$ 单位（仅影响该层的节点值，其他层不受影响）。
2. 将与值为 $X$ 的节点处于同一层的所有节点循环平移 $K$ 单位（这些节点的子树也会随之移动）。
3. 输出从值为 $X$ 的节点到根节点的简单路径上经过的所有节点的值。
正的 $K$ 表示向右循环平移，负的 $K$ 表示向左循环平移。
保证至少有一个类型 $3$ 的询问。
输入格式
第一行包含一个整数 $Q$（$1 \leq Q \leq 10^{5}$）。
接下来 $Q$ 行，每行一个询问：
- 类型 $1$ 和 $2$ 的询问格式为：$T\ X\ K$（$1 \leq T \leq 2$；$1 \leq X \leq 10^{18}$；$0 \leq |K| \leq 10^{18}$），其中 $T$ 表示询问类型。
- 类型 $3$ 的询问格式为：$3\ X$（$1 \leq X \leq 10^{18}$）。
输出格式
对于每个类型 $3$ 的询问，输出从该节点到根节点路径上所有节点的值，按从大到小的顺序输出。
说明/提示
以下是第一组测试数据中前 $4$ 层树的图片：
原始状态：
经过询问 $1\ 2\ 1$ 后：
经过询问 $2\ 4\ -1$ 后：
由 ChatGPT 4.1 翻译