如果你其他$\text{Ynoi}$还没有刷完建议不要来刷这道题，因为：
实际上，这是一道正宗的计算几何题。
Part.1
没什么好说的，既然都知道这是一道计算几何题，请先自行学习计算几何的基础知识。
你需要掌握的有：向量的加，减，叉积，凸包的求法（极角排序）。
以下是下文中点（或向量）的定义：
struct Point //点
{
ll x,y;
Point(ll x=0,ll y=0) : x(x),y(y) {}
Point operator + (const Point &a) const {return Point(x+a.x,y+a.y);} //加
Point operator - (const Point &a) const {return Point(x-a.x,y-a.y);} //减
ll operator * (const Point &a) const {return x*a.y-y*a.x;} //叉积
};
凸包的定义：
struct Hull //凸包
{
Point *st;
int now,top;
Point& operator [] (const int &x) const {return st[x];}
inline void insert(const Point &a) const{st[a.x].y=max(st[a.x].y,a.y);} //更新最优点
inline void push(const Point &a) {st[++top]=a;} //加入一个点
inline void init(int x) //预处理，长度为x的答案对应其位置，方便insert
{
for(int i=1;i<=x;++i)
st[i]=Point(i,-inf);
top=x;
}
inline void Convex() //求新凸包
{
if(top<=2) return;
int lim=top;top=2;
for(int i=3;i<=lim;++i)
{
if(st[i].y==-inf) continue;
while(top>1&&(st[top]-st[top-1])*(st[i]-st[top-1])>=0) --top;
st[++top]=st[i];
}
}
inline ll Getnow()
{
while(now!=top&&add*st[now].x+st[now].y<add*st[now+1].x+st[now+1].y) ++now; //离线保证单增，移动指针即可
return st[now].x*add+st[now].y;
}
};
看不懂可以先跳过，下面要用了再来看，主要一些小函数下面可能没有讲。
这个题的的新知识有：闵可夫斯基和合并凸包。
问题：给你两个点集A,B，产生一个新点集C,满足对任意点$(x_1,y_1)\in A$，$(x_2,y_2)\in B$，得到一个$(x_1+x_2,y_1+y_2)\in C$。
然后知道A，B的凸包，求C的凸包。
这不是很简单吗，暴力枚举直接做。
我们需要一个复杂度为$O(n)$的算法。
我们画个图手玩一下，发现新的凸包就是原来的两个凸包的边重新极角排序一边（网上有图我就不放了）。
证明我不会，可以看一下这个题，感性理解一下，毕竟这里是讲数据结构的。
于是我们得到了一个很有用的结论，求凸包只需要求原来的凸包，然后在一起重新排序就可以了。
但直接重排有点浪费，由于原来两个凸包都已经求好了，于是可以类似归并排序，重新归并一次，代码如下：
inline void Minkowski(Hull &c,Hull &a,Hull &b) //闵可夫斯基和合并凸包
{
int i=1,j=1;c.insert(a[1]+b[1]);
while(i!=a.top&&j!=b.top)
{
((a[i+1]-a[i])*(b[j+1]-b[j])<0)?++i:++j;
c.insert(a[i]+b[j]);
}
while(i!=a.top) ++i,c.insert(a[i]+b[j]);
while(j!=b.top) ++j,c.insert(a[i]+b[j]);
}
凸包存的是点，我们比较a中当前的边与b中当前的边，看一下谁角度更小，然后加入即可，且加入点的原来的点的和。
很简单是不是？
下面开始我们今天的数据结构部分。
Part.2
最大子段和？
很简单啊，$O(n)$扫一遍。
区间最大子段和，单点修改？
做过小白逛公园的都知道（没做过还来$\text{Ynoi}$）这是一个经典问题。哪来那么多经典问题
线段树。
每个点维护一个$lmx,rmx,mmx,sum$，即最大左子段和，最大右子段和，最大子段和，区间和。
合并很简单吧（默认大家都会）。
一个封装好的结构体长这样：
struct Node //答案节点
{
ll lmx,rmx,mmx,sum;
Node(ll lmx,ll rmx,ll mmx,ll sum) : lmx(lmx),rmx(rmx),mmx(mmx),sum(sum) {}
Node() {}
Node operator + (const Node &x) const
{
return Node(max(lmx,sum+x.lmx),max(x.rmx,x.sum+rmx),max(rmx+x.lmx,max(mmx,x.mmx)),sum+x.sum);
}
};
下面的重载运算符即是合并两个答案。
时间复杂度$O(nlogn)$
区间最大子段和，全局加？
先考虑打标记。
显然不行
主要原因是无法通过新的标记快速更新线段树的节点。
然后就没法做？
换个思路。
Part.3
线段树的四个信息肯定还是必须要维护的。
$sum$照旧维护。
我们考虑对于维护长度为$x$的$lmx,rmx,mmx$，实际上这就是一些二维点$(x,ans(x))$
我们可以发现，当我们给这个节点整体加了一个数$add$，那么$ans(x)$就变成了$ans(x)+x*add$，但显然对于我们的这些二维的点，肯定只有一部分是有用的，如果一个点被另一个点压制，那么它就肯定没有用。那么哪些点是有用的呢？相信看到这里大概都明白了，实际上就是这些点的凸包上的点。
所以我们改成维护$lmx,rmx,mmx$三个凸包。
Part.4
首先先解决$lmx,rmx$两个凸包，由于两个等价，只考虑$lmx$。
先看一下我们原来的$lmx$的转移方程
lmx[u]=max(lmx[u<<1],sum[u<<1]+lmx[u<<1|1]);
改成凸包后，我们就是先给右儿子的$lmx$凸包加上一个点$(len_{lson},sum_{lson})$，然后与右凸包合并，代码长这样：
inline void merge(Hull &c,Hull &a,Hull &b,const Point &now) //合并前后缀的凸包
{
for(int i=1;i<=a.top;++i) c.push(a[i]);
for(int i=1;i<=b.top;++i) c.push(b[i]+now);
c.Convex(); //求新凸包
}
$now$就是$(len_{lson},sum_{lson})$，代码就是先把两个凸包加进去，然后求新凸包。
inline void Convex() //求新凸包
{
if(top<=2) return;
int lim=top;top=2;
for(int i=3;i<=lim;++i)
{
if(st[i].y==-inf) continue;
while(top>1&&(st[top]-st[top-1])*(st[i]-st[top-1])>=0) --top;
st[++top]=st[i];
}
}
由于原来就有序，所以可以直接求不用排序。
注意$st$数组中始终$top\le i$，所以可以不用辅助空间。
Part.5
观察$mmx$的转移方程：
mmx[u]=max(max(mmx[u<<1],mmx[u<<1|1]),rmx[u<<1]+lmx[u<<1|1]);
对于$mmx$的凸包，我们先用左右儿子的$mmx$更新一下：
mmx[u].st++;mmx[u].init(r-l+1);
for(int i=1;i<=mmx[u<<1].top;++i) mmx[u].insert(mmx[u<<1][i]);
for(int i=1;i<=mmx[u<<1|1].top;++i) mmx[u].insert(mmx[u<<1|1][i]);
然后$lmx[u<<1]+rmx[u<<1|1]$，怎么处理呢？
是不是觉得还有什么没有登场？
没错，我们的闵可夫斯基和！
仔细想一想，假设有$(x_1,ans(x_1))\in lmx[u<<1]\;\;(x_2,ans(x_2))\in rmx[u<<1|1]$，就会得到一个新的点$x_1+x_2,ans(x_1+x_2))\in mmx[u]$！
于是我们一次闵可夫斯基和合并凸包就可以了，代码长这样：
inline void Minkowski(Hull &c,Hull &a,Hull &b) //闵可夫斯基和合并凸包
{
int i=1,j=1;c.insert(a[1]+b[1]);
while(i!=a.top&&j!=b.top)
{
((a[i+1]-a[i])*(b[j+1]-b[j])<0)?++i:++j;
c.insert(a[i]+b[j]);
}
while(i!=a.top) ++i,c.insert(a[i]+b[j]);
while(j!=b.top) ++j,c.insert(a[i]+b[j]);
}
然后就完了。
Part.6
不还没完
我们光求了一堆凸包，怎么用啊？
这还不简单，直接在凸包上二分即可。
然而你仔细想想，这样的复杂度是多少？
$O(nlog^2n)$
由于这是$\text{Ynoi}$，不是让你$AC$的地方，所以你需要优化。
怎么优化？
我们考虑离线，想一想，凸包有一个好的性质，它上面的点是单调的，我们可以知道从一开始到这个点一共全局加了多少，然后我们按这个把询问排序，由于我们加的值是单增的，所以我们直接每次从上次的位置开始向右扫凸包，因为答案绝对不可能向前走，所以我们的均摊时间就变成了$O(nlogn)$。
于是你就可以快乐的去$AC$此题了！
具体实现借鉴了shadowice1984大佬的方法，把同一层的线段树节点空间分配在一起，减小访问压力。
凸包使用了指针，也可以用$vector$。
$\text{Code}$
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll add,a[maxn];
int n,m;
struct Point //点
{
ll x,y;
Point(ll x=0,ll y=0) : x(x),y(y) {}
Point operator + (const Point &a) const {return Point(x+a.x,y+a.y);} //加
Point operator - (const Point &a) const {return Point(x-a.x,y-a.y);} //减
ll operator * (const Point &a) const {return x*a.y-y*a.x;} //叉积
};
struct Hull //凸包
{
Point *st;
int now,top;
Point& operator [] (const int &x) const {return st[x];}
inline void insert(const Point &a) const{st[a.x].y=max(st[a.x].y,a.y);} //更新最优点
inline void push(const Point &a) {st[++top]=a;} //加入一个点
inline void init(int x) //预处理，长度为x的答案对应其位置，方便insert
{
for(int i=1;i<=x;++i)
st[i]=Point(i,-inf);
top=x;
}
inline void Convex() //求新凸包
{
if(top<=2) return;
int lim=top;top=2;
for(int i=3;i<=lim;++i)
{
if(st[i].y==-inf) continue;
while(top>1&&(st[top]-st[top-1])*(st[i]-st[top-1])>=0) --top;
st[++top]=st[i];
}
}
inline ll Getnow()
{
while(now!=top&&add*st[now].x+st[now].y<add*st[now+1].x+st[now+1].y) ++now; //离线保证单增，移动指针即可
return st[now].x*add+st[now].y;
}
};
struct Node //答案节点
{
ll lmx,rmx,mmx,sum;
Node(ll lmx,ll rmx,ll mmx,ll sum) : lmx(lmx),rmx(rmx),mmx(mmx),sum(sum) {}
Node() {}
Node operator + (const Node &x) const
{
return Node(max(lmx,sum+x.lmx),max(x.rmx,x.sum+rmx),max(rmx+x.lmx,max(mmx,x.mmx)),sum+x.sum);
}
};
struct SegmentTree //线段树
{
Point lmx_base[20][maxn<<1],rmx_base[20][maxn<<1],mmx_base[20][maxn<<1];
Point *lmx_top[20],*rmx_top[20],*mmx_top[20];
Hull lmx[maxn<<2],rmx[maxn<<2],mmx[maxn<<2]; //凸包维护可能的答案
ll sum[maxn<<2];
SegmentTree()
{
for(int i=0;i<20;++i)
lmx_top[i]=lmx_base[i],rmx_top[i]=rmx_base[i],mmx_top[i]=mmx_base[i];
}
inline void merge(Hull &c,Hull &a,Hull &b,const Point &now) //合并前后缀的凸包
{
for(int i=1;i<=a.top;++i) c.push(a[i]);
for(int i=1;i<=b.top;++i) c.push(b[i]+now);
c.Convex(); //求新凸包
}
inline void Minkowski(Hull &c,Hull &a,Hull &b) //闵可夫斯基和合并凸包
{
int i=1,j=1;c.insert(a[1]+b[1]);
while(i!=a.top&&j!=b.top)
{
((a[i+1]-a[i])*(b[j+1]-b[j])<0)?++i:++j;
c.insert(a[i]+b[j]);
}
while(i!=a.top) ++i,c.insert(a[i]+b[j]);
while(j!=b.top) ++j,c.insert(a[i]+b[j]);
}
void build(int u,int l,int r,int dep=0)
{
lmx[u].st=lmx_top[dep];rmx[u].st=rmx_top[dep];mmx[u].st=mmx_top[dep];
if(l==r)
{
lmx[u][1]=rmx[u][1]=mmx[u][1]=Point(0,0); //不选则为0
lmx[u][2]=rmx[u][2]=mmx[u][2]=Point(1,a[l]);sum[u]=a[l];
lmx[u].top=rmx[u].top=mmx[u].top=2;
}
else
{
int mid=(l+r)>>1;
build(u<<1,l,mid,dep+1);build(u<<1|1,mid+1,r,dep+1);
sum[u]=sum[u<<1]+sum[u<<1|1]; //维护和
merge(lmx[u],lmx[u<<1],lmx[u<<1|1],Point(mid-l+1,sum[u<<1]));
merge(rmx[u],rmx[u<<1|1],rmx[u<<1],Point(r-mid,sum[u<<1|1])); //合并前后缀凸包
mmx[u].st++;mmx[u].init(r-l+1); //为不选预留位置
for(int i=1;i<=mmx[u<<1].top;++i) mmx[u].insert(mmx[u<<1][i]);
for(int i=1;i<=mmx[u<<1|1].top;++i) mmx[u].insert(mmx[u<<1|1][i]);
Minkowski(mmx[u],rmx[u<<1],lmx[u<<1|1]); //合并子段和凸包
mmx[u].st--;mmx[u][1]=Point(0,0);mmx[u].top++;mmx[u].Convex(); //不选则为0
}
lmx[u].now=rmx[u].now=mmx[u].now=1;
lmx_top[dep]=lmx[u].st+lmx[u].top;
rmx_top[dep]=rmx[u].st+rmx[u].top;
mmx_top[dep]=mmx[u].st+mmx[u].top;
}
Node query(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return Node(lmx[u].Getnow(),rmx[u].Getnow(),mmx[u].Getnow(),sum[u]+(r-l+1)*add);
int mid=(l+r)>>1;
if(y<=mid) return query(u<<1,l,mid,x,y);
if(x>mid) return query(u<<1|1,mid+1,r,x,y);
return query(u<<1,l,mid,x,y)+query(u<<1|1,mid+1,r,x,y);
}
}wife;
struct Query
{
int l,r,id;
ll val;
Query(int l=0,int r=0,int id=0,ll val=0) : l(l),r(r),id(id),val(val) {}
bool operator < (const Query &x) const {return val<x.val;}
}q[maxn<<1];
int tot;
ll ans[maxn<<1];
template<typename T>
inline void read(T &x)
{
char c;int f=1;
while(!isdigit(c=getchar())) (c=='-')&&(f=-1);
x=c^48;
while(isdigit(c=getchar())) x=x*10+(c^48);
x*=f;
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1,opt,l,r;i<=m;++i)
{
read(opt);read(l);
if(opt==1) add+=l;
else read(r),++tot,q[tot]=Query(l,r,tot,add);
}
sort(q+1,q+tot+1);
add=q[1].val;
for(int i=1;i<=tot;++i) q[i].val-=add;
for(int i=1;i<=n;++i) a[i]+=add; //这里使得所有的q[i].val均为正整数
wife.build(1,1,n);
for(int i=1;i<=tot;++i)
add=q[i].val,ans[q[i].id]=wife.query(1,1,n,q[i].l,q[i].r).mmx;
for(int i=1;i<=tot;++i)
printf("%lld\n",ans[i]);
return 0,QAQ;
}
做完了珂以去做一下这个（不是