暴如力 分如块

因为我的电脑内存很小 我还要玩原神 所以直接分块
分块+懒标记=无敌（

#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
signed a[200005];
int blocks[505], lazytag[505];
int len, tmp, l, r, val;
void modify(int l, int r, int val){
	if(r - l < len){//不足一块
		for(int i = l; i <= r; i++){
			blocks[i / len] += val;
			a[i] += val;
		}
		return;
	}
	for(int i = l / len + 1; i < r / len; i++){//整块 
		blocks[i] += len * val;
		lazytag[i] += val;
	}
	for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块 
		blocks[i / len] += val;
		a[i] += val;
	}
	for(int i = max(r / len * len, l + 1); i <= r; i++){
		blocks[i / len] += val;
		a[i] += val;
	}
}
int query(int l, int r){
	int ct = 0;
	if(r - l < len){//不足一块
		for(int i = l; i <= r; i++){
			ct += a[i] + lazytag[i / len];
		}
		return ct;
	}
	for(int i = l / len + 1; i < r / len; i++){//整块 
		ct += blocks[i];
	}
	for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块 
		ct += a[i] + lazytag[i / len];
	}
	for(int i = max(r / len * len, l + 1); i <= r; i++){
		ct += a[i] + lazytag[i / len];
	}
	return ct;
}
signed main(){
	int n, m;
	cin >> n >> m;
	len = sqrt(n);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		blocks[i / len] += a[i];
	}
	while(m--){
		cin >> tmp;
		if(tmp == 1){
			cin >> l >> r >> val;
            if(l > r) swap(l, r);
			modify(l, r, val);
		}else if(tmp == 2 || tmp == 3){
			cin >> val;
			modify(1, 1, (tmp == 2 ? val : -val));
		}else if(tmp == 4){
			cin >> l >> r;
            if(l > r) swap(l, r);
			cout << query(l, r) << endl;
		}else{
			cout << query(1, 1) << endl;
		}
	}

	return 0;
}

时间复杂度：$O(\sqrt{n})$（常数特小）