P14834 [THUPC 2026 初赛] 庭中有奇树

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。 题解等资源可在 查看。

mej 先生的庭院里有一棵奇树。 这棵树上每个点都有一个正整数编号，且以编号为 $1$ 的点为根，所有正整数都作为点的编号在这棵树上出现过。同时，编号为 $i$ 的点恰好有 $i$ 个子节点，并且这 $i$ 个子节点的编号是连续的：记 $\text{mn}(i)$ 为 $i$ 号节点的子节点中编号最小的、$\text{mx}(i)$ 为最大的，则 $\text{mx}(i) −\text{mn}(i) = i−1$ 且 $\text{mn}(i)$ ∼ $\text{mx}(i)$ 中所有数都恰好出现一次。不仅如此，对于任意的 $1\le i\lt j$，都有 $\text{mx}(i)\lt \text{mn}(j)$。 可以发现以上性质唯一确定了这棵奇树。例如，$1$ 号节点的子节点有 $2$，$2$ 号节点的子节点有 $3$、$4$，$3$ 号节点的子节点有 $5$、$6$、$7$，等等。不过因为 mej 先生不喜欢无限大的树，所以他只保留了这棵树上编号在 $1$ ∼ $n$ 之间的节点。 mej 先生可以从这棵奇树上获取法力。具体来说，树上每个节点都有一个魔力值，初始时所有节点的魔力值都为 $0$；他可以选择一个节点 $x$ 开始获取法力，此时他将会获得 $x$ 的子树中（包括 $x$）所有节点魔力值的异或和的法力。同时他还会对这棵树进行维护，每次他会选择一个节点 $x$ 和一个值 $c$，然后施加法术，将 $x$ 的子树中所有节点的魔力值按位或上 $c$。 现在，mej 先生一共进行了 $q$ 次操作，每次操作可能是维护奇树或者获取法力。他想知道，他每次获取法力时获取的法力值是多少。

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

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

### 【样例 1 解释】 初始时所有节点的魔力值都为 $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$。