C l r d:区间 \([L,R]\) 中的数都加 d ,同时当前的时间戳加 1。
Q l r:查询当前时间戳区间 \([L,R]\) 中所有数的和 。
H l r t:查询时间戳 \(t\) 区间 \([L,R]\) 的和 。
B t:将当前时间戳置为 \(t\)
每次记下版本 \(times\)
保留标记…每次标记的时候直接加上\(tag_p\) 即可
#include <bits/stdc++.h>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define rep(i , j , k) for(int i = j ; i <= k ; i ++)
#define Rep(i , j , k) for(int i = j ; i >= k ; i --)
using namespace std ;
using ll = long long ;
using pii = pair <int , int> ;
using vii = vector <int> ;
#define int long long
auto ot = [&]() { cerr << "ATS TXDY" << '\n' ; int ATS_nantf_txdy = true ; } ;
auto _ios = [&]() { ios :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ; } ;
namespace stO_ATS_Orz {
template < class T > void cmax(T & x , T y) { if(x < y) x = y ; }
template < class T > void cmin(T & x , T y) { if(x > y) x = y ; }
template < class T > void abs(T x) { if(x < 0) x = -x ; }
const int N = 1e5 + 10 ;
int n , m ;
int a[N] , cnt = 0 ;
int rt[N] , tag[N * 50] , sum[N * 50] ;
int ls[N * 50] , rs[N * 50] ;
void build(int l , int r , int & p) {
p = ++ cnt ;
if(l == r) { sum[p] = a[l] ; return ; }
int mid = l + r >> 1 ;
build(l , mid , ls[p]) ;
build(mid + 1 , r , rs[p]) ;
sum[p] = sum[ls[p]] + sum[rs[p]] ;
}
void change(int a , int b , int l , int r , int pre , int & p , int val) {
tag[p = ++ cnt] = tag[pre] ; sum[p] = sum[pre] + 1ll * (min(b , r) - max(a , l) + 1) * val ;
if(a <= l && r <= b) { tag[p] += val ; ls[p] = ls[pre] ; rs[p] = rs[pre] ; return ; }
int mid = l + r >> 1 ;
if(a <= mid) change(a , b , l , mid , ls[pre] , ls[p] , val) ;
else ls[p] = ls[pre] ;
if(b > mid) change(a , b , mid + 1 , r , rs[pre] , rs[p] , val) ;
else rs[p] = rs[pre] ;
}
int query(int a , int b , int l , int r , int p) {
if(a <= l && r <= b) { return sum[p] ; }
int mid = l + r >> 1 , ans = 0 ;
if(a <= mid) ans += query(a , b , l , mid , ls[p]) ;
if(b > mid) ans += query(a , b , mid + 1 , r , rs[p]) ;
ans += 1ll * tag[p] * (min(b , r) - max(a , l) + 1) ;
return ans ;
}
void main() {
cin >> n >> m ; rep(i , 1 , n) cin >> a[i] ;
build(1 , n , rt[0]) ;
int times = 0 ;
rep(i , 1 , m) {
char c ; cin >> c ;
if(c == 'C') {
int l , r , d ;
cin >> l >> r >> d ; times ++ ;
change(l , r , 1 , n , rt[times - 1] , rt[times] , d) ;
}
if(c == 'Q') {
int l , r ; cin >> l >> r ;
cout << query(l , r , 1 , n , rt[times]) << '\n' ;
}
if(c == 'H') {
int l , r , t ; cin >> l >> r >> t ;
cout << query(l , r , 1 , n , rt[t]) << '\n' ;
}
if(c == 'B') {
int t ; cin >> t ; times = t ;
}
}
}
}
signed main() {
_ios() ; ot() ;
return stO_ATS_Orz :: main() , 0 ;
}