10pts求调

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long,long long>
#define fi first
#define se second
const int N=2e5;
const int S=505;
int m,n,a[N],t[S];
int op,l,r,k,top[S];
pii p[S][S];
pii tg[S];
int B;
void upd(int l,int r){
	for(int i=l;i<=r;i+=B)top[i/B]=0;
	for(int i=l;i<=r;i++){
		while((top[i/B]>1&&(p[i/B][top[i/B]-1].se-p[i/B][top[i/B]].se)*(p[i/B][top[i/B]].fi-(i-i/B*B+1))<(p[i/B][top[i/B]-1].fi-p[i/B][top[i/B]].fi)*(p[i/B][top[i/B]].se-a[i]))||(top[i/B]==1&&(p[i/B][top[i/B]-1].se-p[i/B][top[i/B]].se)*(p[i/B][top[i/B]].fi-(i-i/B*B+1))==(p[i/B][top[i/B]-1].fi-p[i/B][top[i/B]].fi)*(p[i/B][top[i/B]].se-a[i])))
			top[i/B]--;
		p[i/B][++top[i/B]]={i-i/B*B+1,a[i]};
	}
}
int gt(int i,int k){
	int l=1,r=top[i],mid,ans=0;
	while(l<=r){
		mid=(r+l)/2;
		if(p[i][mid].se-p[i][mid-1].se>k*p[i][mid].fi-p[i][mid-1].fi)l=mid+1,ans=mid;
		else r=mid-1;
	}
	return p[i][ans].se-k*p[i][ans].fi;
}
signed main(){
	cin>>n;
	B=sqrt(n);
	for(int i=0;i<=n/B;i++)p[i][0]={0,-9e18};
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i)a[i]+=a[i-1];
		t[i/B]=max(t[i/B],a[i]);
	}upd(0,n-1);
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>op>>l>>r;
		if(op==0){
			cin>>k;
			if(l/B*B==r/B*B){
				int ad=tg[l/B].fi;
				for(int i=l/B*B;i<(l/B*B+B);i++,ad+=tg[l/B].se)a[i]+=ad;
				tg[l/B]={0,0};
				ad=k;
				for(int i=l;i<=r;i++,ad+=k)a[i]+=ad;
				upd(l/B*B,l/B*B+B-1);
			}
			else{
				int ad=tg[l/B].fi;
				for(int i=l/B*B;i<l/B*B+B;i++,ad+=tg[l/B].se)a[i]+=ad;
				tg[l/B]={0,0};
				ad=tg[r/B].fi;
				for(int i=r/B*B;i<r/B*B+B;i++,ad+=tg[r/B].se)a[i]+=ad;
				tg[r/B]={0,0};
				ad=k;
				for(int i=l;i<l/B*B+B;i++,ad+=k)a[i]+=ad;
				for(int i=l/B+1;i<r/B;i++,ad+=B*k)tg[i].fi+=ad,tg[i].se+=k,t[i]=gt(i,-tg[i].se)+tg[i].fi;
				for(int i=r/B*B;i<=r;i++,ad+=k)a[i]+=ad;
				upd(l/B*B,l/B*B+B-1);
				upd(r/B*B,r/B*B+B-1);
				
			}
		}
		else{
			int ans=-9e18;
			if(l/B*B==r/B*B){
				int ad=tg[l/B].fi;
				for(int i=l/B*B;i<l/B*B+B;i++,ad+=tg[l/B].se)a[i]+=ad;
				tg[l/B]={0,0};
				upd(l/B*B,l/B*B+B-1);
				for(int i=l;i<=r;i++)ans=max(ans,a[i]);
			}
			else{
				int ad=tg[l/B].fi;
				for(int i=l/B*B;i<l/B*B+B;i++,ad+=tg[l/B].se)a[i]+=ad;
				tg[l/B]={0,0};
				upd(l/B*B,l/B*B+B-1);
				ad=tg[r/B].fi; 
				for(int i=r/B*B;i<r/B*B+B;i++,ad+=tg[r/B].se)a[i]+=ad;
				for(int i=l;i<l/B*B+B;i++)ans=max(ans,a[i]);
				for(int i=l/B+1;i<r/B;i++)ans=max(ans,t[i]);
				for(int i=r/B*B;i<=r;i++)ans=max(ans,a[i]);
			}
			cout<<ans<<'\n';
		}
	} 
	return 0;
}