玄关。

RE on #8, #9, #10

#include<bits/stdc++.h>
// #pragma G++ optimize(2)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
const int N=1e5+5;
int n,m;
ll a[N];
int st[N],ed[N],pos[N];
ll sum[N],add[N];
void blockPre() {
	int block=sqrt(n),num=n/block+(n%block);
	for(int i=1;i<=num;i++) {
		st[i]=(i-1)*block+1;
		ed[i]=i*block;
	}
	ed[num]=n;
	for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
	for(int i=1;i<=num;i++)
		for(int j=st[i];j<=ed[i];j++)
			sum[i]+=a[j];
}
void updateAdd(int l,int r,ll d) {
	int p=pos[l],q=pos[r];
	if(p==q) {
		for(int i=l;i<=r;i++) a[i]+=d;
		sum[p]+=d*(r-l+1);
	}
	else {
		for(int i=p+1;i<=q-1;i++) add[i]+=d;
		for(int i=l;i<=ed[p];i++) a[i]+=d;
		sum[p]+=d*(ed[p]-l+1);
		for(int i=st[q];i<=r;i++) a[i]+=d;
		sum[q]+=d*(r-st[q]+1);
	}
}
ll querySum(int l,int r) {
	ll res=0;
	int p=pos[l],q=pos[r];
	if(p==q) {
		for(int i=l;i<=r;i++) res+=a[i];
		res+=add[p]*(r-l+1);
	}
	else {
		for(int i=p+1;i<=q-1;i++) res+=sum[i]+add[i]*(ed[i]-st[i]+1);
		for(int i=l;i<=ed[p];i++) res+=a[i];
		res+=add[p]*(ed[p]-l+1);
		for(int i=st[q];i<=r;i++) res+=a[i];
		res+=add[q]*(r-st[q]+1);
	}
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	blockPre();
	for(int i=1;i<=m;i++) {
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1) {
			ll k;cin>>k;
			updateAdd(l,r,k);
		}
		else cout<<querySum(l,r)<<'\n';
	}
	return 0;
}