AdditionalFile7000.zip

#7000. 「THUPC 2026 初赛」庭中有奇树

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

mej 先生的庭院里有一棵奇树。

这棵树上每个点都有一个正整数编号，且以编号为 $1$ 的点为根，所有正整数都作为点的编号在这棵树上出现过。同时，编号为 $i$ 的点恰好有 $i$ 个子节点，并且这 $i$ 个子节点的编号是连续的：记 $mn(i)$ 为 $i$ 号节点的子节点中编号最小的、 $mx(i)$ 为最大的，则 $mx(i)-mn(i)=i-1$ 且 $mn(i) \sim mx(i)$ 中所有数都恰好出现一次。不仅如此，对于任意的 $1 \leq i<j$ ，都有 $mx(i)<mn(j)$ 。

可以发现以上性质唯一确定了这棵奇树。例如，$1$ 号节点的子节点有 $2$，$2$ 号节点的子节点有 $3, 4, 3$ 号节点的子节点有 $5,6,7$，等等。不过因为 mej 先生不喜欢无限大的树，所以他只保留了这棵树上编号在 $1 \sim n$ 之间的节点。

mej 先生可以从这棵奇树上获取法力。具体来说，树上每个节点都有一个魔力值，初始时所有节点的魔力值都为 $0$；他可以选择一个节点 $x$ 开始获取法力，此时他将会获得 $x$ 的子树中（包括 $x$）所有节点魔力值的异或和的法力。同时他还会对这棵树进行维护，每次他会选择一个节点 $x$ 和一个值 $c$，然后施加法术，将 $x$ 的子树中所有节点的魔力值按位或上 $c$。

现在，mej 先生一共进行了 $q$ 次操作，每次操作可能是维护奇树或者获取法力。他想知道，他每次获取法力时获取的法力值是多少。

输入格式

从标准输入读入数据。

第一行输入两个正整数 $n, q$ $\left(1 \leq n \leq 10^{18}, 1 \leq q \leq 10^{6}\right)$，表示树的大小和操作次数。 接下来 $q$ 行，每行先输入一个正整数 $op$ $\left(o p \in\{1,2\}\right)$，表示操作类型。若 $op=1$，则再输入两个整数 $x, c$ $\left(1 \leq x \leq n, 1 \leq c<2^{60}\right)$，表示将以 $x$ 为根的子树中所有节点的魔力值按位或 $c$；若 $op=2$，则再输入一个正整数 $x$，表示查询以 $x$ 为根的子树中所有节点魔力值的异或和。

输出格式

输出到标准输出。

对于每次查询，输出一个整数，表示所求的异或和。

样例 1

输入

11 6
1 3 931
1 4 209
1 2 28
2 1
1 8 287
2 4

输出

193
479

初始时所有节点的魔力值都为 $0$。

第一次操作，将以 $3$ 为根的子树中所有节点的魔力值按位或 $931$，所有节点的魔力值序列变为 $0,0,931,0,931,931,931,0,0,0,0$；

第二次操作，将以 $4$ 为根的子树中所有节点的魔力值按位或 $209$，所有节点的魔力值序列变为 $0,0,931,209,931,931,931,209,209,209,209$；

第三次操作，将以 $2$ 为根的子树中所有节点的魔力值按位或 $28$，所有节点的魔力值序列变为 $0,28,959,221,959,959,959,221,221,221,221$；

第四次操作，查询以 $1$ 为根的子树中所有节点的魔力值的异或和，即 $0 \oplus 28 \oplus 959 \oplus 221 \oplus 959 \oplus 959 \oplus 959 \oplus 221 \oplus 221 \oplus 221 \oplus 221=193$；

第五次操作，将以 $8$ 为根的子树中所有节点的魔力值按位或 $287$，所有节点的魔力值序列变为 $0,28,959,221,959,959,959,479,221,221,221$；

第六次操作，查询以 4 为根的子树中所有节点的魔力值的异或和，即 $221 \oplus 479 \oplus 221 \oplus 221 \oplus 221=479$ 。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。