P14312 【模板】K-D Tree

**请注意本题不同寻常的时空限制。**

在 $k$ 维空间中，有一个由整点构成的可重集 $S$（初始为空），$S$ 中每个点都有一个权值。记整点 $A$ 的第 $d$ 维坐标为 $x_d(A)$。 你需要维护三种操作： - 操作一：向 $S$ 中插入点 $A$，权值为 $v$。 - 操作二：给定整点 $A$ 与整点 $B$，将满足 $C\in S$ 且 $\forall d\in\{1,2,\cdots,k\},x_d(A)\le x_d(C)\le x_d(B)$ 的所有整点 $C$ 的权值增加 $v$。 - 操作三：给定整点 $A$ 与整点 $B$，查询满足 $C\in S$ 且 $\forall d\in\{1,2,\cdots,k\},x_d(A)\le x_d(C)\le x_d(B)$ 的所有整点 $C$ 权值之和。 **本题强制在线。**

第一行两个整数 $k,m$，表示空间维数与操作次数。 接下来 $m$ 行，每行若干个整数，描述一次操作： - 若第一个整数为 $1$，接下来 $k+1$ 个整数 $x_1'(A),\cdots,x_k'(A),v'$，表示加密后的整点 $A$ 的坐标和权值。 - 若第一个整数为 $2$，接下来 $2k+1$ 个整数 $x_1'(A),\cdots,x_k'(A),x_1'(B),\cdots,x_k'(B),v'$，表示加密后的整点 $A$ 和 $B$ 的坐标以及权值增量。 - 若第一个整数为 $3$，接下来 $2k$ 个整数 $x_1'(A),\cdots,x_k'(A),x_1'(B),\cdots,x_k'(B)$，表示加密后的整点 $A$ 和 $B$ 的坐标。 - 对于加密后的数据 $a'$，原数据 $a$ 满足 $a=a'\oplus lst$，其中 $\oplus$ 为按位异或运算，$lst$ 为上次操作三的答案（初始为 $0$）。

若干行，每行一个整数，依次为所有操作三的答案。

#### 「样例解释 #1」 :::info[解密后的输入] ```txt 2 10 1 1 4 2 3 1 5 5 5 1 4 2 5 1 2 4 2 2 1 3 3 4 2 3 2 4 5 4 3 1 2 4 3 1 2 1 2 3 2 2 3 4 3 1 2 4 4 ``` ::: 最后一次询问的范围包含 $(1,4),(4,2),(2,4)$ 三个整点，他们的权值之和为 $(2+2)+5+(2+2)=13$。 --- #### 「样例解释 #2」 :::info[解密后的输入] ```txt 3 9 1 1 3 2 3 1 4 3 1 5 1 4 4 4 2 1 2 1 5 3 3 2 3 1 3 4 5 1 5 5 4 3 2 5 5 3 6 6 6 1 3 1 2 1 4 5 5 3 3 3 3 5 5 4 ``` ::: 最后一次询问的范围包含 $(4,4,4),(5,5,4)$ 两个整点，他们的权值之和为 $2+(3+1)=6$。 --- #### 「数据范围」 对于所有测试数据，保证： - 操作一满足解密后的 $1\le x_i(A)\le 10^{18}$ 且 $1\le v\le 10^5$； - 操作二满足解密后的 $1\le x_i(A)\le x_i(B)\le 10^{18}$ 且 $1\le v\le 10^5$； - 操作三满足解密后的 $1\le x_i(A)\le x_i(B)\le 10^{18}$。 |子任务|$k=$|$m\le$|特殊性质|分值| |:-:|:-:|:-:|:-:|:-:| |$1$|$2$|$1.5\times 10^5$|不含操作二|$25$| |$2$|^|^|无|$25$| |$3$|$3$|$10^5$|不含操作二|$25$| |$4$|^|^|无|$25$| **请注意 $\bm{k}$ 与 $\bm{m}$ 没有同时达到各自数据范围的上界。**