题目传送门
题意分析
显然是维护一棵可持久化线段树。
\(1\leq n,m\leq 10^5\)，很容易写完。但是发现空间限制 \(\text{64MB}\)，需要卡空间。
先丢掉线段树中存储的节点边界，放入递归中传参。
然后考虑继续卡，将可持久化线段树的懒标记改为标记永久化，这样可以避免每次 down 都要新建两个节点。（当然你写回收也可以，不过不好写。）
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e5,M=1e5;
int n,a[N+1];
struct segTree{int root[M+1],size;struct node{ll value,tag;int lChild,rChild;}t[N*25+1];int create(node x){t[++size]=x;return size;}int clone(int p){t[++size]=t[p];return size;}void up(int p){t[p].value=t[t[p].lChild].value+t[t[p].rChild].value;}int build(int l,int r){int p=create({});if(l==r){t[p].value=a[l];return p;}int mid=l+r>>1;t[p].lChild=build(l,mid);t[p].rChild=build(mid+1,r);up(p);return p;}int add(int p,int L,int R,int l,int r,int x){p=clone(p);t[p].value+=(min(r,R)-max(l,L)+1ll)*x;if(l<=L&&R<=r){t[p].tag+=x;return p;}int mid=L+R>>1;if(l<=mid){t[p].lChild=add(t[p].lChild,L,mid,l,r,x);}if(mid+1<=r){t[p].rChild=add(t[p].rChild,mid+1,R,l,r,x);}return p;}void add(int v,int i,int l,int r,int x){root[i]=add(root[v],1,n,l,r,x);}ll query0(int p,int L,int R,int l,int r){if(l<=L&&R<=r){
// cout<<t[p].value<<" vbvbbvbvbbvk\n";return t[p].value;}ll ans=t[p].tag*(min(R,r)-max(L,l)+1ll);
// cout<<"l="<<L<<" r="<<R<<" ans="<<ans<<" s="<<l<<" t="<<r<<" hqewuhwqiudquiwhuiwqhduwqhiud\n"; int mid=L+R>>1; if(l<=mid){ans+=query0(t[p].lChild,L,mid,l,r);}if(mid+1<=r){ans+=query0(t[p].rChild,mid+1,R,l,r);}
// cout<<"l="<<L<<" r="<<R<<" ans="<<ans<<"\n";return ans;}ll query(int i,int l,int r){return query0(root[i],1,n,l,r);}void clear(){size=0;}
}t;
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int m;while(cin>>n>>m){t.clear();for(int i=1;i<=n;i++){cin>>a[i];}t.root[0]=t.build(1,n);int time=0;while(m--){char op;int l,r,x;cin>>op;switch(op){case 'C':cin>>l>>r>>x;time++;t.add(time-1,time,l,r,x);break;case 'Q':cin>>l>>r;cout<<t.query(time,l,r)<<'\n';break;case 'H':cin>>l>>r>>x;cout<<t.query(x,l,r)<<'\n';break;case 'B':cin>>x;time=x;break;}}cout<<'\n';} cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}