题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4348
题目大意：
维护几种操作而已，
操作1：对于每次改变序列的操作都增加当前时间，
操作2：返回到指定时间，
操作3：查询过去时间序列的区间和
题目分析：
这道题首先空间需求需要计算好，
因为不是和以前的查询区间第k小那样
每次只增加一条链的空间，这次的空间需要开的稍微大点。
然后就是不难想到对每个新增的时间点建线段树，懒惰标记也要用到，
但是对于这道题懒惰标记不能下推，因为下推到的点可能之前没有新建过！
所以我们采取另一种手段来实现修改查询操作，
就是每次在区间直接对区间答案进行修改，
然后如果被划分到刚刚好的区间的时候打上lazy即可。简单谈下个人对这样的做法的理解（我也是网上学的T_T）：
对于一次的修改L,R,C,lazy的标记只存在与L,R之间划分到的整区间,
并且所有不是整区间的区间答案都整体增加了该有的值，包括整区间，
然后每次查询答案其答案的初始化都是当前区间的lazy值乘上其区间大小，
因为如果当前区间有lazy那么一定是整体覆盖的，并且查询和修改
要把目标区间进行划分，这样我们不难发现，
每次查询和修改都能维护出合理的答案，原理证明挺难讲的T_T.....
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=150010;
const int ub=1e6;
const double inf=1e-4;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
维护几种操作而已，
操作1：对于每次改变序列的操作都增加当前时间，
操作2：返回到指定时间，
操作3：查询过去时间。题目分析：
这道题首先空间需求需要计算好，
因为不是和以前的查询区间第k小那样
每次只增加一条链的空间，这次的空间需要开的稍微大点。
然后就是不难想到对每个新增的时间点建线段树，懒惰标记也要用到，
但是对于这道题懒惰标记不能下推，因为下推到的点可能之前没有新建过！
所以我们采取另一种手段来实现修改查询操作，
就是每次在区间直接对区间答案进行修改，
然后如果被划分到刚刚好的区间的时候打上lazy即可。简单谈下个人对这样的做法的理解（我也是网上学的T_T）：
对于一次的修改L,R,C,lazy的标记只存在与L,R之间划分到的整区间,
并且所有不是整区间的区间答案都整体增加了该有的值，包括整区间，
然后每次查询答案其答案的初始化都是当前区间的lazy值乘上其区间大小，
因为如果当前区间有lazy那么一定是整体覆盖的，并且查询和修改
要把目标区间进行划分，这样我们不难发现，
每次查询和修改都能维护出合理的答案，原理证明挺难讲的T_T.....*/int n,m,a[maxn],b[maxn],cnt;
char op[5];ll sum[maxn<<4],lazy[maxn<<4];
int rt[maxn<<4],L[maxn<<4],R[maxn<<4],tot=0;
void build(int& o,int l,int r){o=++tot,sum[o]=0,lazy[o]=0;if(l==r){sum[o]=a[l];return;}int mid=l+r>>1;build(L[o],l,mid);build(R[o],mid+1,r);sum[o]=sum[L[o]]+sum[R[o]];///区间合并
}
void update(int& o,int pre,int l1,int r1,int l2,int r2,ll c){///这里不能用懒惰标记代替o=++tot,sum[o]=sum[pre];L[o]=L[pre],R[o]=R[pre],lazy[o]=lazy[pre];///sum[o]+=1LL*(r2-l2+1)*c;if(l2<=l1&&r1<=r2){lazy[o]+=c;return ;}int mid=l1+r1>>1;if(r2<=mid) update(L[o],L[pre],l1,mid,l2,r2,c);else if(mid<l2) update(R[o],R[pre],mid+1,r1,l2,r2,c);else{update(L[o],L[pre],l1,mid,l2,mid,c);update(R[o],R[pre],mid+1,r1,mid+1,r2,c);}
}
ll query(int o,int l1,int r1,int l2,int r2){if(l2<=l1&&r1<=r2) return sum[o];int mid=l1+r1>>1;ll ans=1LL*(r2-l2+1)*lazy[o];if(r2<=mid) ans+=query(L[o],l1,mid,l2,r2);else if(mid<l2) ans+=query(R[o],mid+1,r1,l2,r2);else{ans+=query(L[o],l1,mid,l2,mid);ans+=query(R[o],mid+1,r1,mid+1,r2);}return ans;
}int main(){while(scanf("%d%d",&n,&m)!=EOF){cnt=0;mst(sum,0),mst(lazy,0);rep(i,1,n+1) scanf("%d",&a[i]);tot=0;build(rt[0],1,n);int cur=0,x,y;ll z;while(m--){scanf("%s",op);if(op[0]=='C'){scanf("%d%d%lld",&x,&y,&z);cur++;update(rt[cur],rt[cur-1],1,n,x,y,z);}else if(op[0]=='Q'){scanf("%d%d",&x,&y);printf("%lld\n",query(rt[cur],1,n,x,y));}else if(op[0]=='H'){scanf("%d%d%lld",&x,&y,&z);printf("%lld\n",query(rt[z],1,n,x,y));}else if(op[0]=='B'){scanf("%d",&x);cur=x;}}}return 0;
}