版权声明：本文为博主原创文章，未经博主允许不得转载。
题意：
一个长度为n的数组，4种操作 ：
（1）C l r d：区间[l,r]中的数都加1，同时当前的时间戳加1 。
（2）Q l r：查询当前时间戳区间[l,r]中所有数的和 。
（3）H l r t：查询时间戳t区间[l,r]的和 。
（4）B t：将当前时间戳置为t 。
所有操作均合法 。
解法：
很明显是一道主席树的题 。
对于每一次区间加法都新建节点建一棵线段树，加个懒惰标记就行了，查询的话直接线段树区间求和 。
不过感觉这一题就是为可持续化数据结构写的，特别是时间戳这一点，当前时间戳的版本就是从上一个时间戳继承下来的，而且所有记录都保存了下来，好神奇，感觉对主席树的理解又加深了一点 。
code 主席树
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#define ll long long using namespace std; const int N=+; int root[N],tot;
int Ls[N*],Rs[N*],add[N*];
ll sum[N*]; int n,m; inline int bulidtree(int L,int R){
int k=tot++;
add[k]=; if (L==R){
scanf("%lld",&sum[k]);
return k;
} int mid=(L+R)>>;
Ls[k]=bulidtree(L,mid);
Rs[k]=bulidtree(mid+,R); sum[k]=sum[Ls[k]]+sum[Rs[k]]; return k;
} inline int update(int o,int L,int R,int x,int LL,int RR){
int k=tot++;
Ls[k]=Ls[o]; Rs[k]=Rs[o]; add[k]=add[o]; sum[k]=sum[o]; sum[k]+=(ll)x*(R-L+); if (LL==L && RR==R){
add[k]+=x;
return k;
} int mid=(LL+RR)>>;
if (R<=mid) Ls[k]=update(Ls[k],L,R,x,LL,mid);
else if (L>mid) Rs[k]=update(Rs[k],L,R,x,mid+,RR);
else {
Ls[k]=update(Ls[k],L,mid,x,LL,mid);
Rs[k]=update(Rs[k],mid+,R,x,mid+,RR);
} return k;
} inline ll query(int o,int L,int R,int LL,int RR){
if (L==LL && R==RR) return sum[o]; int mid=(LL+RR)>>; ll ret=(ll)add[o]*(R-L+); if (R<=mid) return ret+query(Ls[o],L,R,LL,mid);
else if (L>mid) return ret+query(Rs[o],L,R,mid+,RR);
else return ret+query(Ls[o],L,mid,LL,mid)+query(Rs[o],mid+,R,mid+,RR);
} int main(){
int x,L,R;
int now;
char ch[]; bool f=false; while (~scanf("%d%d",&n,&m)){
if (f) puts("");
else f=true; tot=;
root[]=bulidtree(,n);
now=; while (m--){
scanf("%s",ch);
if (ch[]=='C') {
scanf("%d%d%d",&L,&R,&x);
now++;
root[now]=update(root[now-],L,R,x,,n);
}
else if (ch[]=='Q') {
scanf("%d%d",&L,&R);
printf("%lld\n",query(root[now],L,R,,n));
}
else if (ch[]=='H'){
scanf("%d%d%d",&L,&R,&x);
printf("%lld\n",query(root[x],L,R,,n));
}
else if (ch[]=='B') {
scanf("%d",&now);
}
}
} return ;
}