C++(g++ 7.5.0) 解法, 执行用时: 245ms, 内存消耗: 7440K, 提交时间: 2022-10-28 18:01:57

#include <bits/stdc++.h>
using namespace std;
#define ls (p << 1)
#define rs (p << 1 | 1)
const int N = 1e5 + 10;
typedef long long ll;
ll tr[N<<2][2], lazy[N<<2];

void down(int s, int t, int p){
	if(lazy[p]){
		int mid = s + t >> 1;
		tr[ls][0] += lazy[p] * (mid - s + 1);
		lazy[ls] += lazy[p];
		tr[ls][1] += lazy[p];
		tr[rs][0] += lazy[p] * (t - mid);
		lazy[rs] += lazy[p];
		tr[rs][1] += lazy[p];
		lazy[p] = 0;
	}
}
void up(int p){
	tr[p][0] = tr[ls][0] + tr[rs][0];
	tr[p][1] = min(tr[ls][1], tr[rs][1]);
}
void md(int l, int r, int s, int t, int p, ll k){
	if(s == t){
		tr[p][0] += k;
		tr[p][0] = max(tr[p][0], 0ll);
		tr[p][1] = tr[p][0];
		return;
	}
	if(l <= s && r >= t){
		if(tr[p][1] >= -k){
			tr[p][0] += k * (t - s + 1);
			lazy[p] += k;
			tr[p][1] += k;
			return;
		}
	}
	down(s, t, p);
	int mid = s + t >> 1;
	if(l <= mid) md(l, r, s, mid, ls, k);
	if(r > mid) md(l, r, mid + 1, t, rs, k);
	up(p);
}
ll ask(int l, int r, int s, int t, int p){
	if(l <= s && r >= t) return tr[p][0];
	int mid = s + t >> 1;
	down(s, t, p);
	ll res = 0;
	if(l <= mid) res += ask(l, r, s, mid, ls);
	if(r > mid) res += ask(l, r, mid + 1, t, rs);
	return res; 
}
int main()
{
	int n, q;
	cin >> n >> q;
	while(q--){
		ll m;
		int l, r;
		scanf("%lld%d%d", &m, &l, &r);
		if(m == 0) printf("%lld\n", ask(l, r, 1, n, 1));
		else md(l, r, 1, n, 1, m);
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 629ms, 内存消耗: 5464K, 提交时间: 2023-05-17 15:17:42

#include <bits/stdc++.h>
#define int long long
using namespace std;
int f[400001],v[400001];


void insertTree(int k, int l, int r, int x, int y, int z){
	if(l >= x && y >= r && (z > 0 || f[k] == 0 || v[k] + z >= 0)){
		if(z > 0 || v[k] + z >= 0) v[k] += z, f[k] += (r - l + 1) * z;
		return;
	}
	if(l == r) {
		f[k] = 0, v[k] = 0;
		return;
	}
	int m = (l + r) >> 1;
	f[k + k] += v[k] * (m -l +1);
	f[k + k + 1] += v[k] * (r - m);
	if(v[k]) 
		v[k + k] += v[k], v[k + k + 1] += v[k], v[k] = 0;
	if(x <= m) insertTree(k + k, l, m, x, y, z);
	if(y > m) insertTree(k + k + 1, m + 1, r, x, y, z);
	f[k] = f[k + k] + f[k + k + 1];
}


int calc(int k, int l, int r, int x, int y){
	
	
	if(l >= x && r <= y) return f[k] ;
	int m = (l + r) >> 1;
	f[k + k] += v[k] * (m -l +1);
	f[k + k + 1] += v[k] * (r - m);
	if(v[k]) 
		v[k + k] += v[k], v[k + k + 1] += v[k], v[k] = 0;
	int res = 0;
	if(x <= m) res += calc(k + k, l, m, x, y);
	if(y > m) res += calc(k + k + 1, m + 1, r, x, y);
	return res;
}


signed main(){
	int m, n;
	cin>>n>>m;
	while(m--){
		int t, x, y;
		cin>>t>>x>>y;
		if(!t) 
			cout<<calc(1, 1, n, x, y)<<endl;
		else
			insertTree(1, 1, n, x, y, t);
	}
}