题意：
给定一个长度为1 e 5的数组，有1 e 5次操作，操作有下面四种：
Clrd: 将[ l , r ]的值都加d，时间增加1
Qlr: 询问当前时间[ l , r ]的区间和
Hlrt: 询问t时间[ l , r ]的区间和
Bt :回到t时刻，并且t时刻之后的操作都不计
思路：
由于有不同时刻的数组，即对应不同个历史版本，考虑用主席树
但是这样，主席树进行p u s h d o w n操作的时候，公用节点都被修改，还是要新建树，空间不够
在结构体里记录一下l a z表示所有子区间的懒惰标记
修改的时候只在上层区间更新l a z,不下传
查询的时候，维护一个a d d，表示自顶向下的l a z的和，每次用a d d ∗ l e n 为区间长度)就是懒惰标记要增加的和；
这是因为对于不同时间公共的节点，不能改变l a z值，还会影响到之前的状态；
这样保证每次修改只会影响到l o g n个节点
空间复杂度：点击跳转
代码：
const int maxn=1e5+7,mod=1e9+7,inf=0x3f3f3f3f; int n,m,root[maxn],idx; ll a[maxn]; struct node{ int l,r; ll sum,laz; }tr[maxn*32]; void pushup(int u,int l,int r){ tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum+tr[u].laz*(r-l+1); } void build(int &now,int l,int r){ now=++idx;//建立新线段树 tr[now].sum=tr[now].laz=0; if(l==r){ tr[now].sum=a[l];return ;///初始化 } int mid=(l+r)/2; build(tr[now].l,l,mid);build(tr[now].r,mid+1,r); pushup(now,l,r); } void update(int &now,int las,int l,int r,int L,int R,int val){ now=++idx;///对于修改的节点新建立一颗树 tr[now]=tr[las];//先复制过来 if(L<=l&&r<=R){//当前区间完全包含待修改区间的话 tr[now].laz+=val;//永久化标记 tr[now].sum+=val*(r-l+1);//求和 return ;///及时返回 已经更新完了 不需要pushup操作 } int mid=(l+r)/2; if(L<=mid) update(tr[now].l,tr[las].l,l,mid,L,R,val); if(R>mid) update(tr[now].r,tr[las].r,mid+1,r,L,R,val); pushup(now,l,r); } ll query(int now,int l,int r,int L,int R,ll add){ //add为路径上的懒惰标记 if(L<=l&&r<=R){ return tr[now].sum+add*(r-l+1);///完全包含的话，值等于和加上标记的内容 } ll ans=0; int mid=(l+r)/2; if(L<=mid) ans+=query(tr[now].l,l,mid,L,R,add+tr[now].laz);//注意沿途加标记 if(R>mid) ans+=query(tr[now].r,mid+1,r,L,R,add+tr[now].laz); return ans; } int main(){ while(~scanf("%d%d",&n,&m)){ idx=0; int time=0; rep(i,1,n) a[i]=read; build(root[0],1,n); rep(i,1,m){ char op[2]; cin>>op; if(op[0]=='C'){ int l=read,r=read,d=read; ++time; update(root[time],root[time-1],1,n,l,r,d); } else if(op[0]=='Q'){ int l=read,r=read; printf("%lld\n",query(root[time],1,n,l,r,0)); } else if(op[0]=='H'){ int l=read,r=read,t=read; printf("%lld\n",query(root[t],1,n,l,r,0)); } else time=read; } } return 0; }
