第一次学分块维护凸包，所以照着某一篇题解写的。但是只有第 11 个点过了，别的都 WA。

求大佬帮调 orz。

代码如下：

#include <bits/stdc++.h>
#define fin(str) freopen(str,"r",stdin)
#define fout(str) freopen(str,"w",stdout)
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int maxlen=325;
const ll inf=1e18;
int n,m;
ll a[maxn];
int len,tot,bl[maxlen],br[maxlen],bel[maxn];
int top,stk[maxn],cov[maxlen][maxlen],cnt[maxlen];
ll fir[maxlen],k[maxlen],add[maxlen];
inline double slope(int x,int y) {return 1.0*(a[x]-a[y])/(x-y); }
inline void buildCOV(int id){
	stk[top=1]=bl[id];
	for (int i=bl[id]+1;i<=br[id];i++){
		if (top>=2 && slope(stk[top-1],stk[top])<slope(stk[top-1],i)) top--;
		stk[++top]=i;
	}
	cnt[id]=top;
	for (int i=1;i<=top;i++) cov[id][i]=stk[i];
	cov[id][0]=0,cov[id][top+1]=n+1;
}
inline void initBLOCK(){
	len=sqrt(n),tot=(n-1)/len+1;
	for (int i=1;i<=tot;i++){
		bl[i]=(i-1)*len+1;
		br[i]=i*len;
	}
	br[tot]=n;
	for (int i=1;i<=tot;i++) for (int j=bl[i];j<=br[i];j++) bel[j]=i;
	for (int i=1;i<=tot;i++) buildCOV(i);
}
inline void pushdown(int id){
	for (int i=bl[id];i<=br[id];i++){
		a[i]+=fir[id]+k[id]*(i-bl[id])+add[id];
	}
	fir[id]=k[id]=add[id]=0;
}
inline void update(int l,int r,ll val){
	int nl=bel[l],nr=bel[r];
	if (nl==nr){
		pushdown(nl);
		for (int i=l;i<=r;i++){
			a[i]+=val*(i-l+1);
		}
		ll d=val*(r-l+1);
		for (int i=r+1;i<=br[nl];i++){
			a[i]+=d;
		}
		buildCOV(nl);
		for (int i=nl+1;i<=tot;i++) add[i]+=d;
		return ;
	}
	ll d=val*(br[nl]-l+2);
	for (int i=nl+1;i<nr;i++){
		fir[i]+=d;
		k[i]+=val;
		d+=val*(br[i]-bl[i]+1);
	}
	pushdown(nl);
	for (int i=l;i<=br[nl];i++){
		a[i]+=val*(i-l+1);
	}
	buildCOV(nl);
	pushdown(nr);
	for (int i=r;i>=bl[nr];i--){
		a[i]+=val*(i-l+1);
	}
	d=val*(r-l+1);
	for (int i=r+1;i<=br[nr];i++) a[i]+=d;
	buildCOV(nr);
	for (int i=nr+1;i<=tot;i++) add[i]+=d;
}
inline ll get(int x){
	if (x<1 || x>n) return -inf;
	int id=bel[x];
	return a[x]+fir[id]+k[id]*(x-bl[id])+add[id];
}
inline ll search(int id){
	int l=1,r=cnt[id];
	while (l<=r){
		int mid=(l+r)>>1;
		ll fl=get(cov[id][mid-1]),fmid=get(cov[id][mid]),fr=get(cov[id][mid+1]);
		if (fl<fmid && fmid<fr) l=mid+1;
		else{
			if (fl>fmid && fmid>fr) r=mid-1;
			else return fmid; 
		}
	}
	return -inf;
}
inline ll query(int l,int r){
	int nl=bel[l],nr=bel[r];
	if (nl==nr){
		ll res=-inf;
		for (int i=l;i<=r;i++) res=max(res,get(i));
		return res;
	}
	ll res=-inf;
	for (int i=nl+1;i<=nr-1;i++) res=max(res,search(i));
	for (int i=l;i<=br[nl];i++) res=max(res,get(i));
	for (int i=r;i>=bl[nr];i--) res=max(res,get(i));
	return res;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
	a[0]=a[n+1]=inf;
	initBLOCK();
	scanf("%d",&m);
	for (int i=1,opt,l,r,x;i<=m;i++){
		scanf("%d",&opt);
		if (!opt){
			scanf("%d%d%d",&l,&r,&x);
			update(l,r,1ll*x);
		}else{
			scanf("%d%d",&l,&r);
			printf("%lld\n",query(l,r));
		}
	}
	return 0;
}