题意
对于各个以往的历史版本实现以下操作：
- 在第 p 个数后插入数 x 。
- 删除第 p 个数。
- 翻转区间 [l,r]，例如原序列是 \(\{5,4,3,2,1\}\)，翻转区间 [2,4] 后，结果是 \(\{5,2,3,4,1\}\)。
- 查询区间 [l,r]中所有数的和。
做法：可持久化treap
定义
typedef pair<int,int> Pair;
结构体
struct Node {
int key, val, l, r, sum, size;// 键值 随机值 左子 右子 和 子树大小
bool rev;
void clear() { 全部清空 }
};
struct Treap{
int pool[], pooler;//内存池
Node t[];//树上的点
int root[];//
int now, all;//当前版本数 最新版本数
Treap() : now(0), pooler(0) {
pool[i]赋值为i
root[now] = pool[++pooler];
}
函数...
}
函数
int newroot(){内存池吐点}
int newnode(int x){
内存池吐点， 赋值(key = x, val, l, r, sum, size)
}
void delnode(int x){
点x清空, 内存池吞点
}
void next(){
新建根 复制根 now = all //更新至最新版本
}
void back(int x){
now = x; //回到原来的版本
}
void update(int x){维护sum, size}
void pushdown(int x){
下推rev标记
比如左边就是新建一个节点然后把左节点所有信息都复制上去
然后打rev标记
另一边同理
}
Pair split(int x, int p){
从以x为根的子树里切p大小的左部分
返回值{左部分根，右（即剩余）部分根}
如果size == p那么返回make_pair(x, 0);
如果size[l] + 1 == p那么返回make_pair(x, r);
先复制一下当前根
根据大小递归操作
记得update新子树根
并把(当前子树根+右子树)和左部分根合并哦（反之亦然）
}
void rev(int l, int r){
把树切成三块 中间那块是要翻转的
新建一个点为中间那块的根，把它打上rev标记
然后合并三棵树
更新root[now];
}
结束辣