分块+凸包
求出前缀和数组s
对于l~r加上k，相当于s[l]~s[r]加上一个首项为k，公差为k的等差数列。r~n加上k*(r-l+1)。
分块之后对每一块维护两个标记，一个记录它加的等差数列（两个等差数列相加仍是等差数列），一个记录它整体加的值。
设首项的标记为A,公差为B
查询一块的最大值，就是询问最大的 s[i] + i*B
可以看成询问平面上的若干横坐标为i,纵坐标为si,斜率为B的直线的最大纵截距，那么维护一个上凸壳即可。
对于散点修改后暴力重构凸包。
对于询问在凸包上三分。
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=2e5+7;
typedef long long LL;
typedef double db;
using namespace std;
int n,m,bl[N],sz,tot,top[350];
LL s[N],lz[350],A[350],B[350];
template<typename T>void read(T &x) {
char ch=getchar(); x=0; T f=1;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}
struct pt {
LL x,y;
pt(){}
pt(LL x,LL y):x(x),y(y){}
friend bool operator <(const pt&A,const pt&B) {
return A.x<B.x||(A.x==B.x&&A.y<B.y);
}
}p[N],q[350][350],D;
pt operator - (const pt&A,const pt&B) { return pt(A.x-B.x,A.y-B.y); }
LL cross(pt A,pt B) { return A.x*B.y-A.y*B.x; }
LL dot(pt A,pt B) { return A.x*B.x+A.y*B.y; }
LL length(pt A) { return dot(A,A); }
void make_ham(int id,int l,int r) {
For(i,l,r) p[i]=pt(i,s[i]);
int tp=0;
q[id][++tp]=p[l];
For(i,l+1,r) {
while(tp>1&&cross(q[id][tp]-q[id][tp-1],p[i]-q[id][tp-1])>=0) tp--;
q[id][++tp]=p[i];
}
top[id]=tp;
}
void get_pre() {
sz=sqrt(n); tot=n/sz; if(n%sz) tot++;
For(i,1,n) {
bl[i]=(i-1)/sz+1;
p[i]=pt(i,s[i]);
}
For(i,1,tot) {
int dn=(i-1)*sz+1,up=min(n,i*sz);
make_ham(i,dn,up);
}
}
void down(int x) {
int l=(x-1)*sz+1,r=min(n,x*sz);
if(lz[x]) {
For(i,l,r) s[i]+=lz[x];
lz[x]=0;
}
if(A[x]||B[x]) {
For(i,l,r) s[i]+=A[x]+B[x]*(i-l);
A[x]=B[x]=0;
}
}
void change(int l,int r,LL k) {
down(bl[l]);
down(bl[r]);
if(bl[l]==bl[r]) {
For(i,l,r) s[i]+=k*(i-l+1);
For(i,r+1,bl[l]*sz) s[i]+=k*(r-l+1);
make_ham(bl[l],(bl[l]-1)*sz+1,min(bl[l]*sz,n));
For(i,bl[l]+1,tot) lz[i]+=k*(r-l+1);
return;
}
For(i,l,min(n,bl[l]*sz)) s[i]+=k*(i-l+1);
make_ham(bl[l],(bl[l]-1)*sz+1,min(bl[l]*sz,n));
For(i,bl[l]+1,bl[r]-1) {
A[i]+=k*((i-1)*sz+1-l+1); B[i]+=k;
}
For(i,(bl[r]-1)*sz+1,min(n,bl[r]*sz)) {
if(i<=r) s[i]+=k*(i-l+1);
else s[i]+=k*(r-l+1);
}
For(i,bl[r]+1,tot) lz[i]+=k*(r-l+1);
make_ham(bl[r],(bl[r]-1)*sz+1,min(bl[r]*sz,n));
}
LL calc(int x) { return s[x]+lz[bl[x]]+A[bl[x]]+B[bl[x]]*(x-(bl[x]-1)*sz-1); }
LL get_ans(int x) {
int l=1,r=top[x];
while(l<=r) {
if(l+1>=r) return max(calc(q[x][l].x),calc(q[x][r].x));
int mid=((l+r)>>1);
LL a=calc(q[x][mid-1].x),b=calc(q[x][mid].x),c=calc(q[x][mid+1].x);
if(a<b&&b<c) l=mid+1;
else if(a>b&&b>c) r=mid-1;
else return b;
}
return 0;
}
LL qry(int l,int r) {
LL rs=-1e18;
if(bl[l]==bl[r]) {
For(i,l,r) rs=max(rs,calc(i));
return rs;
}
For(i,l,min(n,bl[l]*sz)) rs=max(rs,calc(i));
For(i,bl[l]+1,bl[r]-1)
rs=max(rs,get_ans(i));
For(i,(bl[r]-1)*sz+1,r) rs=max(rs,calc(i));
return rs;
}
#define DEBUG
int main() {
#ifdef DEBUG
freopen("2388.in","r",stdin);
freopen("2388.out","w",stdout);
#endif
read(n);
For(i,1,n) read(s[i]),s[i]+=s[i-1];
get_pre();
read(m);
while(m--) {
int o,l,r; LL v;
read(o); read(l); read(r);
if(!o) {
read(v);
change(l,r,v);
}
else printf("%lld
",qry(l,r));
}
return 0;
}
/*
20
32 -5 -28 -1 -39 30 44 38 -44 -6 -8 33 -45 -4 39 -32 -28 -6 42 -24
20
0 7 19 48
0 7 13 5
1 13 17
*/