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

题目背景

这是一道模板题。

题目描述

您需要写一种数据结构,来维护一个序列,其中需要提供以下操作(**对于各个以往的历史版本**): 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,opt_i$,$v_i$ 表示基于的过去版本号 $(0\le v_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$,$-10^6