问题描述:
写一种数据结构，用来维护一个序列。需要提供以下操作（对于各个以往的历史版本）：
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≤ 200000，内存限制为 1GB。
| 输入样例 | 输出样例 |
| 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 | 3 4 5 10 |
可持久化文艺平衡树
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
struct node{int ls,rs,val,pri,size,lazy; ll sum;}t[(N<<7)];
int cnt = 0;
int new_node(int x){
cnt++;
t[cnt].size = 1; t[cnt].ls = t[cnt].rs = 0;
t[cnt].val = x; t[cnt].sum = x; t[cnt].pri = rand(); //val是节点数值，sum是该节点的左右节点和本节点的总和
t[cnt].lazy = 0;
return cnt;
}
int clone(int u){ //克隆树u。不需要复制整棵树，只复制根就行
int ret = new_node(0);
t[ret] = t[u]; //复制
return ret;
}
void Update(int u){ //向上更新
t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum + t[u].val;
}
void push_down(int u){ //向下更新
if(!t[u].lazy) return;
if(t[u].ls != 0) t[u].ls = clone(t[u].ls); //翻转前克隆左区间
if(t[u].rs != 0) t[u].rs = clone(t[u].rs); //翻转前克隆右区间
swap(t[u].ls,t[u].rs); //翻转区间
t[t[u].ls].lazy^=1; t[t[u].rs].lazy^=1; //标记向下传递
t[u].lazy = 0; //标记清除
}
void Split(int u,int x,int &L,int &R){ //排名分裂
if(u == 0){L = R = 0; return ;}
push_down(u);
if(t[t[u].ls].size+1 <=x){ //第x个数在u的右子树上
L = clone(u); //这个时间点的L，它是这个时间点的u的克隆
Split(t[L].rs, x-t[t[u].ls].size-1, t[L].rs,R);
Update(L);
}
else{
R = clone(u); //这个时间点的R，它是这个时间点的u的克隆
Split(t[R].ls,x,L,t[R].ls);
Update(R);
}
}
int Merge(int L,int R){ //合并
if(L==0 || R==0) return L+R;
push_down(L); push_down(R);
if(t[L].pri > t[R].pri){ t[L].rs = Merge(t[L].rs,R); Update(L); return L;}
else { t[R].ls = Merge(L,t[R].ls); Update(R); return R;}
}
int root[N];
int main(){
srand(time(NULL));
int version=0; int L,p,R; ll x,y;
for(int i=0;i<N;i++) root[i] = 0;
ll lastans=0; //强制在线规则
int n; cin >> n;
while(n--){
int v,op; cin >> v >> op; //过去版本号，操作序号
if(op==1){ //在第x个数后插入y
cin >>x >>y; x^=lastans;y^=lastans;
Split(root[v],x,L,p);
root[++version]=Merge(Merge(L,new_node(y)),p); //记录在新的时间点上
}
if(op==2){ //删除第x个数
cin >>x; x^=lastans;
Split(root[v],x,L,R); Split(L,x-1,L,p);
root[++version] = Merge(L,R); //记录在新的时间点上
}
if(op==3){ //翻转区间[x,y]
cin >>x >>y; x^=lastans; y^=lastans;
Split(root[v],y,L,R); Split(L,x-1,L,p);
t[p].lazy ^= 1;
root[++version] = Merge(Merge(L,p),R); //记录在新的时间点上
}
if(op==4){ //查询区间和[x, y]
cin >> x >> y; x^=lastans; y^=lastans;
Split(root[v],y,L,R); Split(L,x-1,L,p); //p树是区间[x,y]
lastans = t[p].sum;
cout << lastans << endl;
root[++version]=Merge(Merge(L,p),R); //记录在新的时间点上
}
}
return 0;
}
笔记：可持久化需要记录这棵树在每个时间点的形态，为了减少储存空间，只克隆变化的部分。强制在线的规则是需要取得上一个 操作的答案，按照异或运算在能获得本次的真实数字。历史版本储存在旧的时间点上，需要时通过root[]提取根来操作，再将结果记录在新的节点上。