题意分析
显然是维护一棵可持久化线段树。
$1\leq n,m\leq 10^5$，很容易写完。但是发现空间限制 $\text{64MB}$，需要卡空间。
先丢掉线段树中存储的节点边界，放入递归中传参。
然后考虑继续卡，将可持久化线段树的懒标记改为标记永久化，这样可以避免每次 down 都要新建两个节点。（当然你写回收也可以，不过不好写。）
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//#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;
}
