题意：首先给你n个数，开始时间为0，最后按照操作输出
给你四种操作：
1. C l r d : 在（l，r）区间都加上d，时间加一
2. Q l r : 询问现在（l，r）的区间和
3. H l r t : 询问在t的时间（l，r）的区间和
4. B t : 直接回到t的时间
题解：首先是区间修改区间查询，可以想到线段树，接着就是询问历史版本与回到历史版本，这样就是主席树了
首先我们知道普通主席树是单点修改，并支持历史版本的区间求和与回到历史版本（就是这删除之后的树），仅仅只是因为它存了多棵线段树
而我们这儿是要进行区间修改，所以第一反应就是模拟线段树的lazy标记，并在查询时再更新再建树，但是这样会卡空间
因此我们需要这样想，模拟lazy标记进行重建树（最多建立2*log2（n）个节点）是必须的，但是查询时就不需要重建树了
这样我们就需要记录两个值：sum代表这一段中被增加区间的与此这一段的区间相交的总和，com代表这一段都需要增加这么多
这时我们查询时就需要每次加上com与待查询的区间相交的值（加上之前更新的），最后再包含的区间里加上sum再减去这儿com与待查询的区间相交的值（重复了）
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const ll INF=1ll<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=1e5+7; int root[Max],tot; struct node { int lef,rig; ll sum,com;//相交总共的和 这一段每个点都加上这个 }msegtr[Max*40]; ll pre[Max];//把原来的数放入前缀和里，主席树里仅仅更新修改的值 void Init(int &cnt) { cnt=0; msegtr[0].lef=msegtr[0].rig=0; msegtr[0].sum=msegtr[0].com=0ll; root[0]=0,tot=0; pre[0]=0ll; return; } int Jud(int sta,int enn,int lef,int rig)//关键的区间交 { return max(min(rig,enn)-max(lef,sta)+1,0); } void Create(int sta,int enn,int &x,int y,int lef,int rig,int com) { msegtr[++tot]=msegtr[y]; msegtr[tot].sum+=(ll)com*Jud(sta,enn,lef,rig); x=tot; if(sta>=lef&&enn<=rig)//模拟线段树区间更新 { msegtr[tot].com+=com;//这一段每个点都加上这个 return; } int mid=dir(sta+enn,1); if(mid>=lef) Create(sta,mid,msegtr[x].lef,msegtr[y].lef,lef,rig,com); if(mid<rig) Create(mid+1,enn,msegtr[x].rig,msegtr[y].rig,lef,rig,com); return; } ll Query(int sta,int enn,int x,int lef,int rig) { if(sta>=lef&&enn<=rig) { return msegtr[x].sum-msegtr[x].com*Jud(sta,enn,lef,rig);//多加了，要减去 } int mid=dir(sta+enn,1); ll ans=0ll; if(mid>=lef) { ans+=Query(sta,mid,msegtr[x].lef,lef,rig)+msegtr[msegtr[x].lef].com*Jud(sta,mid,lef,rig);//加上区间交的值 } if(mid<rig) { ans+=Query(mid+1,enn,msegtr[x].rig,lef,rig)+msegtr[msegtr[x].rig].com*Jud(mid+1,enn,lef,rig); } return ans; } int main() { int n,m,temp,cnt; int lef,rig,sum; char str[10]; while(~scanf("%d %d",&n,&m)) { Init(cnt); for(int i=1;i<=n;++i) { scanf("%d",&temp); pre[i]=pre[i-1]+temp; } for(int i=0;i<m;++i) { scanf("%s",str); if(str[0]=='C') { scanf("%d %d %d",&lef,&rig,&sum); Create(1,n,root[cnt+1],root[cnt],lef,rig,sum); cnt++; } else if(str[0]=='Q') { scanf("%d %d",&lef,&rig); printf("%I64d ",Query(1,n,root[cnt],lef,rig)+pre[rig]-pre[lef-1]); } else if(str[0]=='H') { scanf("%d %d %d",&lef,&rig,&sum); printf("%I64d ",Query(1,n,root[sum],lef,rig)+pre[rig]-pre[lef-1]); } else { scanf("%d",&sum); if(sum<cnt) { tot=root[sum+1]; cnt=sum;//存储线段树，这样就代表摧毁了后面更新的树 } } } } return 0; }