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

题目背景

这是一道模板题。

题目描述

您需要写一种数据结构,来维护一个序列,其中需要提供以下操作(**对于各个以往的历史版本**): 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$ 的查询操作,输出一行一个数表示区间的和。

输入输出样例

输入样例 #1

10
0 1 0 1
1 1 1 2
2 4 1 2
3 1 2 0
4 4 2 1
5 3 5 7
6 4 5 6
4 1 7 1
8 3 4 6
9 4 4 1

输出样例 #1

3
4
5
10

说明

**强制在线:以下针对 $p_i, x_i, l_i, r_i$ 的限制均是按位异或 $lastans$ 后的限制。** 对于 $30\%$ 的数据,$n \le 5000$。 对于另外 $30\%$ 的数据,$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$。