)
此题可以作为可持久化线段树区间修改的模板题，于罗勇军老师的《算法竞赛上册》4.4 可持久化线段树的区间更新部分被简单提及了一嘴 —— 说是按标准主席树编码即可，然而并没有给出具体做法，
可能是不想限制大家的想法吧
。
但实际上也并不是直接按照标准主席树编码那么简单，这种需要可持久化的区间操作引入了一个新的操作 —— 标记永久化，话不多说，直接进入主题。
题解
简化题意
给定一个长度为
的序列
以及
个操作，操作有如下四种：
，
，
，
：给
内的每个数加上
，并将时间
加
。
，
，
：查询当前
内所有数的和。
，
，
，
：查询
时，
内所有数的和。
，
：返回时间
。
其中，当前时间
初始为
；只有操作
才会使
增加；如果选择返回时间
，则
之后的操作全部作废。
思路
当读到查询历史时间的区间和时，会发现这题需要可持久化，并且
就是每个树根的编号。
那么考虑如何实现区间修改。
首先，区间操作为了防止爆时间，懒标记肯定时需要的。但如果像普通线段树一样，每次访问到一个结点就下传标记，那么会使得历史结点的值被改变。
怎么办呢？
方法一
容易想到的一种方案是：
每次下传的时候创建两个子结点，继承上一个版本的信息后再下传懒标记。显然，这一方案十分的正确，然而这题仅给了 64M 的空间，把这个单次操作产生的空间约为
的方案 pass 掉了。
所以得考虑另一种方法，就是 标记永久化。
方法二 - 标记永久化
什么是标记永久化？就是字面意思，将懒标记打完以后就放在那个结点再也不动了，会被新版本继承，但不会再被下传，这样就避免了更改历史结点的问题。
然后就是如何利用标记永久化求和：
这样想，如果直接询问根节点，那么子结点的标记肯定没法计算，所以上传操作 (即 updata) 仍然需要；如果有一个结点存在标记，那么它的整棵子树都要增加数值，若询问的区间在它子树内，而标记又不能下传，难以直接计算，所以开一个变量 Sum_Tag 来记录经过该结点时增量，通过 Sum_Tag 统计从根一路到达目标区间的增量。
如此一来，单次操作产生的空间约为
，在满足空间需求的条件下实现了区间修改和查询。
代码
思路讲完了，更具体的细节见代码：
#include
#include
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,T;
ll a[N];
int tid,rt[N];
struct Tree{
int ls,rs,tag;
ll sum;
Tree() {ls=rs=sum=tag=0;}
}tr[N*25];
#define mid ((l+r)>>1)
void updata(int p,int l,int r){
int ls=tr[p].ls;
int rs=tr[p].rs;
tr[p].sum=tr[ls].sum+tr[rs].sum+(r-l+1)*tr[p].tag;//加上自身区间的增量
}
void build(int &p,int l,int r){
p=++tid;
if(lr){
tr[p].sum=a[l];
return ;
}
build(tr[p].ls,l,mid);
build(tr[p].rs,mid+1,r);
updata(p,l,r);
}
void modify(int lp,int &p,int l,int r,int x,int y,ll v){
p=++tid;
tr[p]=tr[lp];
if(x<=l&&r<=y){
tr[p].tag+=v;
tr[p].sum+=(r-l+1)v;
return ;
}
if(x<=mid) modify(tr[lp].ls,tr[p].ls,l,mid,x,y,v);
if(mid<y) modify(tr[lp].rs,tr[p].rs,mid+1,r,x,y,v);
updata(p,l,r);
}
ll query(int p,int l,int r,int x,int y,ll Sum_Tag){//通过Sum_Tag累计从根到目标区间的所有增量
if(x<=l&&r<=y) return tr[p].sum+Sum_Tag(r-l+1);//添加累计增量
ll ans=0;
//进入子区间时才给Sum_Tag增加自身的tag
if(x<=mid) ans+=query(tr[p].ls,l,mid,x,y,Sum_Tag+tr[p].tag);
if(mid<y) ans+=query(tr[p].rs,mid+1,r,x,y,Sum_Tag+tr[p].tag);
return ans;
}
#undef mid
int main(){
while(scanf(“%d%d”,&n,&m)!=EOF){
for(int i=1;i<=n;i++){
scanf(“%lld”,&a[i]);
}
T=tid=0;
build(rt[T],1,n);
char op;
int l,r,d,t;
for(int i=1;i<=m;i++){
cin>>op;
if(op’C’){
scanf(“%d%d%d”,&l,&r,&d);
modify(rt[T],rt[T+1],1,n,l,r,d);
T++;
}
else if(op==‘Q’){
scanf(“%d%d”,&l,&r);
printf(“%lld\n”,query(rt[T],1,n,l,r,0));
}
else if(op==‘H’){
scanf(“%d%d%d”,&l,&r,&t);
printf(“%lld\n”,query(rt[t],1,n,l,r,0));
}
else if(op==‘B’){
scanf(“%d”,&t);
T=t;
}
}
}
return 0;
