传送门
题意：
一个长度为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 。
所有操作均合法 。
题解
原来……主席树真的能做可持久化的啊……花了一个下午才搞明白……（虽然是看题解的）
先考虑一下，如果直接每一次修改的话，一共要修改$r-l+1$次，空间复杂度绝对爆炸
然后考虑一下线段树的打懒标记，可不可以套到主席树上来？
我们发现可以这么做，于是每一次修改区间时，如果区间相等，直接打上标记，等到查询的时候，再把标记给加上去
ps：更改时间的时候可以直接把$cnt$改成$rt[t+1]-1$，这样的话可以回收空间
1 //minamoto 2 #include<bits/stdc++.h> 3 #define ll long long 4 using namespace std; 5 const int N=100005,M=N*30; 6 int n,m,cnt,rt[N]; 7 int L[M],R[M];ll sum[M],add[M]; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 inline ll read(){ 11 #define num ch-'0' 12 char ch;bool flag=0;ll res; 13 while(!isdigit(ch=getc())) 14 (ch=='-')&&(flag=true); 15 for(res=num;isdigit(ch=getc());res=res*10+num); 16 (flag)&&(res=-res); 17 #undef num 18 return res; 19 } 20 void build(int &now,int l,int r){ 21 add[now=++cnt]=0; 22 if(l==r) return (void)(sum[now]=read()); 23 int mid=(l+r)>>1; 24 build(L[now],l,mid); 25 build(R[now],mid+1,r); 26 sum[now]=sum[L[now]]+sum[R[now]]; 27 } 28 void update(int last,int &now,int l,int r,int ql,int qr,int x){ 29 now=++cnt; 30 L[now]=L[last],R[now]=R[last],add[now]=add[last],sum[now]=sum[last]; 31 sum[now]+=1ll*x*(qr-ql+1); 32 if(ql==l&&qr==r) return (void)(add[now]+=x); 33 int mid=(l+r)>>1; 34 if(qr<=mid) update(L[last],L[now],l,mid,ql,qr,x); 35 else if(ql>mid) update(R[last],R[now],mid+1,r,ql,qr,x); 36 else return (void)(update(L[last],L[now],l,mid,ql,mid,x),update(R[last],R[now],mid+1,r,mid+1,qr,x)); 37 } 38 ll query(int now,int l,int r,int ql,int qr){ 39 if(l==ql&&r==qr) return sum[now]; 40 int mid=(l+r)>>1; 41 ll res=1ll*add[now]*(qr-ql+1); 42 if(qr<=mid) res+=query(L[now],l,mid,ql,qr); 43 else if(ql>mid) res+=query(R[now],mid+1,r,ql,qr); 44 else res+=query(L[now],l,mid,ql,mid)+query(R[now],mid+1,r,mid+1,qr); 45 return res; 46 } 47 int main(){ 48 //freopen("testdata.in","r",stdin); 49 n=read(),m=read(); 50 cnt=-1; 51 build(rt[0],1,n); 52 int now=0; 53 while(m--){ 54 char ch;int l,r,x; 55 while(!isupper(ch=getc())); 56 switch(ch){ 57 case 'C':{ 58 l=read(),r=read(),x=read(); 59 ++now; 60 update(rt[now-1],rt[now],1,n,l,r,x); 61 break; 62 } 63 case 'Q':{ 64 l=read(),r=read(); 65 printf("%lld\n",query(rt[now],1,n,l,r)); 66 break; 67 } 68 case 'H':{ 69 l=read(),r=read(),x=read(); 70 printf("%lld\n",query(rt[x],1,n,l,r)); 71 break; 72 } 73 case 'B':{ 74 now=read(); 75 cnt=rt[now+1]-1; 76 break; 77 } 78 } 79 } 80 return 0; 81 }