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$ 即保持原版本无变化），新版本即编号为此次操作的序号。**
**本题强制在线。**
输入格式
无
输出格式
无
说明/提示
**强制在线：以下针对 $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$。