线段树上维护最大子段和是在每个节点上维护四元组 \((mx,lm,rm,sum)\)，但现在有全局加操作，线段树就不能直接维护了。
考虑如何维护 \(lm\)，\(rm\) 同理，设 \(pre(x)\) 为长度为 \(x\) 的前缀和的值，\(add\) 为当前全局加的和，则 \(add \times x + pre(x)\) 是可能成为 \(lm\) 的值，将 \((x,pre(x))\) 看作点对，能成为 \(lm\) 的点都在上凸包上，维护出上凸包后，在凸包上二分即可得到当前最值。
发现 \(mx\) 维护时需要合并 \(rm_{ls}\) 和 \(lm_{rs}\)，这里的合并即为闵可夫斯基和。
若在凸包上二分，复杂度就为 \(O(m\log^2n)\)。将询问离线，按全局加的值排序，即为询问的斜率单调增，直接在凸包上记录一个指针，就能做到 \(O(m\log n)\) 了。
#include<bits/stdc++.h>
#define maxn 1200010
#define inf 100000000000000
#define ls (cur<<1)
#define rs (cur<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
inline char gc()
{
static char now[1<<20],*S,*T;
if(T==S)
{
T=(S=now)+fread(now,1,1<<20,stdin);
if(T==S) return EOF;
}
return *S++;
}
inline int read()
{
int x=0;char c=gc();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return flag?-x:x;
}
template<typename F> inline void write(F x)
{
short st[30],tp=0;
if(x<0) putchar('-'),x=-x;
do st[++tp]=x%10,x/=10; while(x);
while(tp) putchar('0'|st[tp--]);
putchar('\n');
}
int n,m,root=1,cnt;
ll now;
ll a[maxn],ans[maxn],sum[maxn];
struct Ask
{
int l,r,id;
ll v;
}q[maxn];
bool operator < (const Ask &a,const Ask &b)
{
return a.v<b.v;
}
struct Vec
{
ll x,y;
Vec(ll a=0,ll b=0)
{
x=a,y=b;
}
};
Vec operator + (const Vec &a,const Vec &b)
{
return Vec(a.x+b.x,a.y+b.y);
}
Vec operator - (const Vec &a,const Vec &b)
{
return Vec(a.x-b.x,a.y-b.y);
}
ll operator * (const Vec &a,const Vec &b)
{
return a.x*b.y-a.y*b.x;
}
vector<Vec> operator + (const vector<Vec> &a,const vector<Vec> &b)
{
vector<Vec> c;
for(int i=0;i<a.size();++i) c.push_back(a[i]);
for(int i=0;i<b.size();++i) c.push_back(b[i]);
return c;
}
vector<Vec> operator + (const vector<Vec> &a,const Vec &b)
{
vector<Vec> c;
for(int i=0;i<a.size();++i) c.push_back(a[i]+b);
return c;
}
struct Convex
{
int pos;
vector<Vec> p;
void build()
{
if(p.size()<=2) return;
int top=1;
for(int i=2;i<p.size();++i)
{
while(top&&(p[i]-p[top-1])*(p[top]-p[top-1])<=0) top--;
p[++top]=p[i];
}
while(p.size()>top+1) p.pop_back();
}
void init(ll v)
{
p.push_back(Vec(0,0)),p.push_back(Vec(1,v));
}
void update(Vec a)
{
p[a.x].y=max(p[a.x].y,a.y);
}
ll ask()
{
while(pos<p.size()-1&&now*p[pos].x+p[pos].y<=now*p[pos+1].x+p[pos+1].y) pos++;
return now*p[pos].x+p[pos].y;
}
}mx[maxn],lm[maxn],rm[maxn];
struct node
{
ll mx,lm,rm,sum;
node(ll a=0,ll b=0,ll c=0,ll d=0)
{
mx=a,lm=b,rm=c,sum=d;
}
};
node operator + (const node &a,const node &b)
{
return node(max(a.rm+b.lm,max(a.mx,b.mx)),max(a.lm,a.sum+b.lm),max(b.rm,b.sum+a.rm),a.sum+b.sum);
}
void merge(Convex &a,Convex &b,Convex &c)
{
int i=0,j=0;
c.update(a.p[0]+b.p[0]);
while(i<a.p.size()-1&&j<b.p.size()-1)
{
if((a.p[i+1]-a.p[i])*(b.p[j+1]-b.p[j])<=0) c.update(a.p[++i]+b.p[j]);
else c.update(a.p[i]+b.p[++j]);
}
while(i<a.p.size()-1) c.update(a.p[++i]+b.p[j]);
while(j<b.p.size()-1) c.update(a.p[i]+b.p[++j]);
}
void build(int l,int r,int cur)
{
if(l==r)
{
mx[cur].init(sum[cur]=a[l]),lm[cur].init(a[l]),rm[cur].init(a[l]);
return;
}
build(l,mid,ls),build(mid+1,r,rs),sum[cur]=sum[ls]+sum[rs],mx[cur].p.push_back(Vec(0,0));
lm[cur].p=lm[ls].p+(lm[rs].p+Vec(mid-l+1,sum[ls])),rm[cur].p=rm[rs].p+(rm[ls].p+Vec(r-mid,sum[rs]));
for(int i=1;i<=r-l+1;++i) mx[cur].p.push_back(Vec(i,-inf));
for(int i=0;i<mx[ls].p.size();++i) mx[cur].update(mx[ls].p[i]);
for(int i=0;i<mx[rs].p.size();++i) mx[cur].update(mx[rs].p[i]);
merge(rm[ls],lm[rs],mx[cur]),mx[cur].build(),lm[cur].build(),rm[cur].build();
}
node query(int L,int R,int l,int r,int cur)
{
if(L<=l&&R>=r) return node(mx[cur].ask(),lm[cur].ask(),rm[cur].ask(),sum[cur]+now*(r-l+1));
if(R<=mid) return query(L,R,l,mid,ls);
if(L>mid) return query(L,R,mid+1,r,rs);
return query(L,R,l,mid,ls)+query(L,R,mid+1,r,rs);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=m;++i)
{
int opt,x;
opt=read();
if(opt==1) x=read(),now+=x,ans[i]=-1;
else q[++cnt].v=now,q[cnt].l=read(),q[cnt].r=read(),q[cnt].id=i;
}
build(1,n,root),sort(q+1,q+cnt+1);
for(int i=1;i<=cnt;++i) now=q[i].v,ans[q[i].id]=query(q[i].l,q[i].r,1,n,root).mx;
for(int i=1;i<=m;++i)
if(ans[i]!=-1)
write(ans[i]);
return 0;
}