Problem | Record

本地环境 : GCC 14.1.0 C++20

评测环境 : C++20 -O2

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int n,m;
int block;
long long lazy[maxn];
long long a[maxn],b[maxn],id[maxn];
void add(int l,int r,int c){
	int sid=id[l],eid=id[r];
	if(sid==eid){
		for(int i=l;i<=r;i++){
			a[i]+=c;
			b[sid]+=c;
		}
		return ;
	}
	for(int i=l;id[i]==sid;i++){
		a[i]+=c;
		b[sid]+=c;
	}
	for(int i=sid+1;i<=eid-1;i++){
		lazy[i]+=c;
		b[sid]+=block*c;
	}
	for(int i=r;id[i]==eid;i--){
		a[i]+=c;
		b[eid]+=c;
	}
	return ; 
}
int query(int l,int r){
	int res=0;
	int sid=id[l],eid=id[r];
	if(sid==eid){
		for(int i=l;i<=r;i++){
			res+=a[i];
			res+=lazy[sid];
		}
		return res;
	}
	for(int i=l;id[i]==sid;i++){
		res+=a[i];
		res+=lazy[sid];
	}
	for(int i=sid+1;i<=eid-1;i++){
		res+=b[i];
	}
	for(int i=r;id[i]==eid;i--){
		res+=a[i];
		res+=lazy[eid];
	}
	return res;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	block=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		id[i]=(i-1)/block+1;
		b[id[i]]+=a[i];
	}
	for(int i=1;i<=m;i++){
		int op,x,y,z;
		cin>>op>>x>>y;
		if(op==1){
			cin>>z;
			add(x,y,z);
		}
		else{
			cout<<query(x,y)<<'\n';
		}
	}
	return 0;
}