P5055 【模板】可持久化文艺平衡树

这是一道模板题。

您需要写一种数据结构，来维护一个序列，其中需要提供以下操作（**对于各个以往的历史版本**）： 1. 在第 $p$ 个数后插入数 $x$。 2. 删除第 $p$ 个数。 3. 翻转区间 $[l,r]$，例如原序列是 $\{5,4,3,2,1\}$，翻转区间 $[2,4]$ 后，结果是 $\{5,2,3,4,1\}$。 4. 查询区间 $[l,r]$ 中所有数的和。 **和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本（操作 $4$ 即保持原版本无变化），新版本即编号为此次操作的序号。** **本题强制在线。**

第一行包含一个整数 $n$，表示操作的总数。 接下来 $n$ 行，每行前两个整数 $v_i, \mathrm{opt}_i$，$v_i$ 表示基于的过去版本号（$0 \le v_i < i$），$\mathrm{opt}_i$ 表示操作的序号（$1 \le \mathrm{opt}_i \le 4$）。 若 $\mathrm{opt}_i=1$，则接下来两个整数 $p_i, x_i$，表示操作为在第 $p_i$ 个数后插入数 $x$ 。 若 $\mathrm{opt}_i=2$，则接下来一个整数 $p_i$，表示操作为删除第 $p_i$ 个数。 若 $\mathrm{opt}_i=3$，则接下来两个整数 $l_i, r_i$，表示操作为翻转区间 $[l_i, r_i]$。 若 $\mathrm{opt}_i=4$，则接下来两个整数 $l_i, r_i$，表示操作为查询区间 $[l_i, r_i]$ 的和。 **强制在线规则：** **令当前操作之前的最后一次 $4$ 操作的答案为 $lastans$（如果之前没有 $4$ 操作，则 $lastans=0$）。** **则此次操作的 $p_i,x_i$ 或 $l_i,r_i$ 均按位异或上 $lastans$ 即可得到真实的 $p_i,x_i$ 或 $l_i,r_i$。**

对于每个序号为 $4$ 的查询操作，输出一行一个数表示区间的和。

:::info[样例解释] 样例明文： ``` 10 0 1 0 1 1 1 1 2 2 4 1 2 3 1 1 3 4 4 1 2 5 3 1 3 6 4 1 2 4 1 2 4 8 3 1 3 9 4 1 4 ``` 完成所有操作后总共生成了 $11$ 个版本： 版本 $0$（初始版本）：$\varnothing$ 版本 $1$：$\{1\}$ 版本 $2$：$\{1,2\}$ 版本 $3$：$\{1,2\}$（这个操作查询区间 $\left[1,2\right]$ 的和，输出了 $3$。） 版本 $4$：$\{1,3,2\}$ 版本 $5$：$\{1,3,2\}$（这个操作查询区间 $\left[1,2\right]$ 的和，输出了 $4$。） 版本 $6$：$\{2,3,1\}$ 版本 $7$：$\{2,3,1\}$（这个操作查询区间 $\left[1,2\right]$ 的和，输出了 $5$。） 版本 $8$：$\{1,3,4,2\}$ 版本 $9$：$\{4,3,1,2\}$ 版本 $10$：$\{4,3,1,2\}$（这个操作查询区间 $\left[1,4\right]$ 的和，输出了 $10$。） :::: **强制在线：以下针对 $p_i, x_i, l_i, r_i$ 的限制均是按位异或 $lastans$ 后的限制。** - 对于 $6$ 个测试点，$n \le 5000$。 - 对于另外 $6$ 个测试点，$v_i = i - 1$。 - 欢迎用户加强数据，可联系管理员或出题人。 对于 $100\%$ 的数据，$1 \le n \le 2 \times {10}^5$，$|x_i| < {10}^6$。 假设基于的历史版本的序列长度为 $len \ge 1$，有： 若 $\mathrm{opt}_i=1$，则 $0 \le p_i \le len$。 若 $\mathrm{opt}_i=2$，则 $1 \le p_i \le len$。 若 $\mathrm{opt}_i=3$，则 $1 \le l_i \le r_i \le len$。 若 $\mathrm{opt}_i=4$，则 $1 \le l_i \le r_i \le len$。 假设基于的历史版本的序列长度为 $0$，有： $\mathrm{opt}_i=1$，$p_i=0$。