题目

提交记录

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,l,r,k,cnt;
int xl[200001],xg[200001],ans[200001];
int x[200001],y[200001],fk[200001];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=(int)sqrt(n);i++){
		cnt++;
		x[cnt]=y[cnt-1]+1;
		y[cnt]=x[cnt]+(int)sqrt(n)-1;
		for(int j=x[cnt];j<=y[cnt];j++){
			fk[j]=cnt;
		}
	}
	if(n%(int)sqrt(n)){
		cnt++;
		x[cnt]=y[cnt-1]+1;
		y[cnt]=n;
		for(int i=x[cnt];i<=y[cnt];i++){
			fk[i]=cnt;
		}
	}
	for(int i=1;i<=n;i++){
		cin>>xl[i];
		ans[fk[i]]+=xl[i];
	}
	for(int i=1;i<=m;i++){
		cin>>s;
		if(s==1){
			cin>>l>>r>>k;
			for(int j=l;j<=min(r,y[fk[l]]);j++){
				xl[j]+=k;
				ans[fk[l]]+=k;
			}
			if(fk[l]!=fk[r]){
				for(int j=x[fk[r]];j<=r;j++){
					xl[j]+=k;
					ans[fk[r]]+=k;
				}
			}
			for(int j=fk[l]+1;j<fk[r];j++){
				xg[j]+=k;
				ans[j]+=k*(y[j]-x[j]+1);
			}
		}
		else if(s==2){
			cin>>k;
			xl[1]+=k;
			ans[fk[1]]+=k;
		}
		else if(s==3){
			cin>>k;
			xl[1]-=k;
			ans[fk[1]]-=k;
		}
		else if(s==4){
			cin>>l>>r;
			cnt=0;
			for(int j=l;j<=min(r,y[fk[l]]);j++){
				cnt+=xl[j]+xg[fk[l]];
			}
			if(fk[l]!=fk[r]){
				for(int j=x[fk[r]];j<=r;j++){
					cnt+=xl[j]+xg[fk[r]];
				}
			}
			for(int j=fk[l]+1;j<fk[r];j++){
				cnt+=ans[j];
			}
			cout<<cnt<<endl;
		}
		else{
			cout<<xl[1]+xg[fk[1]]<<endl;
		}
	}
	return 0;
}