```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 305000
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
const int bk=8;
inline int read()
{
int x=0;bool f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar()) x=(x*10)+(c^48);
if(f)x=-x;return x;
}
struct node
{
ll x,y;
node(ll x=0,ll y=0):x(x),y(y){}
};
ll adt,a[maxn],n,m,cnt,b[maxn];
ll operator *(node a,node b){return a.x*b.y-a.y*b.x;}
node operator +(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator -(node a,node b){return (node){a.x-b.x,a.y-b.y};}
node operator -(node b){return (node){-b.x,-b.y};}
void swap(node &a,node &b){node tmp=a;a=b;b=tmp;}
struct tb
{
node *p;int n,pa;
tb(){n=0,pa=1;}
inline node& operator [](const int &k){return p[k];}
inline void up(const node &k){p[k.x].y=max(p[k.x].y,k.y);}
inline void push(const node &k){p[++n]=k;}
inline void pr(int x){for(int i=1;i<=x;i++)p[i]=(node){i,-inf};n=x;}
inline void cl(){n=0,pa=1;}
inline void build()
{
if(n<=2)return ;
int m=n;n=2;
for(int i=3;i<=m;i++)
{
if(p[i].y==-inf)continue;
while(n>1&&(p[n]-p[n-1])*(p[i]-p[n-1])>=0)--n;
p[++n]=p[i];
}
}
inline ll get()
{
while(pa!=n&&adt*p[pa].x+p[pa].y<adt*p[pa+1].x+p[pa+1].y)++pa;
return adt*p[pa].x+p[pa].y;
}
};
struct abc
{
ll sum,pre,sff,ans;
abc operator +(const abc &k)const
{
return (abc){sum+k.sum,max(pre,sum+k.pre),max(k.sff,sff+k.sum),max(max(ans,k.ans),sff+k.pre)};
}
}ans[maxn*2];
struct tree
{
node pe[20][maxn>>2],su[20][maxn>>2],as[20][maxn>>2];
node *pr[20],*sf[20],*an[20];
tb pre[maxn>>1],sff[maxn>>1],ans[maxn>>1];
ll sum[maxn>>1];
void init()
{
for(int i=0;i<20;i++)
pr[i]=pe[i],sf[i]=su[i],an[i]=as[i];
}
inline void merge(tb &p,tb &s1,tb &s2,const node &nw)
{
for(int i=1;i<=s1.n;i++)p.push(s1[i]);
for(int i=1;i<=s2.n;i++)p.push(s2[i]+nw);
p.build();
}
inline void mkfsj(tb &p,tb &s1,tb &s2)
{
int i=1,j=1;p.up(s1[1]+s2[1]);
while(i<=s1.n&&j<=s2.n)
{
((s1[i+1]-s1[i])*(s2[j+1]-s2[j])<0)?i++:j++;
p.up(s1[i]+s2[i]);
}
while(i<=s1.n)i++,p.up(s1[i]+s2[j]);
while(j<=s2.n)j++,p.up(s1[i]+s2[j]);
}
void build(int rt,int l,int r,int dp=0)
{
pre[rt].cl(),sff[rt].cl(),ans[rt].cl();
pre[rt].p=pr[dp],sff[rt].p=sf[dp],ans[rt].p=an[dp];
if(l==r)
{
pre[rt][1]=sff[rt][1]=ans[rt][1]=(node){0,0};
pre[rt][2]=sff[rt][2]=ans[rt][2]=(node){1,a[l]};
sum[rt]=a[l];
pre[rt].n=sff[rt].n=ans[rt].n=2;
}
else
{
int mid=(l+r)>>1;
build(rt<<1,l,mid,dp+1);
build(rt<<1|1,mid+1,r,dp+1);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
merge(pre[rt],pre[rt<<1],pre[rt<<1|1],(node){mid-l+1,sum[rt<<1]});
merge(sff[rt],sff[rt<<1|1],sff[rt<<1],(node){r-mid,sum[rt<<1|1]});
ans[rt].p++;ans[rt].pr(r-l+1);
for(int i=1;i<=ans[rt<<1].n;i++)ans[rt].push(ans[rt<<1][i]);
for(int i=1;i<=ans[rt<<1|1].n;i++)ans[rt].push(ans[rt<<1|1][i]);
mkfsj(ans[rt],sff[rt<<1],pre[rt<<1|1]);
ans[rt].p--;ans[rt][1]=(node){0,0};ans[rt].n++;ans[rt].build();
}
pr[dp]=pre[rt].p+pre[rt].n;
sf[dp]=sff[rt].p+sff[rt].n;
an[dp]=ans[rt].p+ans[rt].n;
}
abc query(int rt,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return (abc){sum[rt]+(r-l+1)*adt,pre[rt].get(),sff[rt].get(),ans[rt].get()};
int mid=(l+r)>>1;
if(qr<=mid)return query(rt<<1,l,mid,ql,qr);
if(ql>mid)return query(rt<<1|1,mid+1,r,ql,qr);
return query(rt<<1,l,mid,ql,qr)+query(rt<<1|1,mid+1,r,ql,qr);
}
}t;
struct bbc
{
ll l,r,i,v;
}u[maxn*2];
bool cmp(bbc a,bbc b)
{
return a.v<b.v;
}
signed main()
{
//freopen("girl.in","r",stdin);
//freopen("mine.out","w",stdout);
n=read(),m=read(),cnt=0;
for(int i=1;i<=n;i++)b[i]=a[i]=read();
for(int i=1;i<=m;i++)
{
int k=read(),l=read();
if(k==1)adt+=l;
else
{
int r=read();
++cnt;
u[cnt]=(bbc){l,r,cnt,adt};
}
}
m=cnt;
sort(u+1,u+m+1,cmp);
adt=u[1].v;
for(int i=1;i<=m;i++)u[i].v-=adt;
for(int i=1;i<=n;i++)b[i]=(a[i]+=adt);
int ln=ceil(1.0*n/bk)+1;
for(ll ii=1;ii<=bk;ii++)
{
ll l=(ii-1)*ln+1,r=ii*ln;
int len=r-l+1;if(len<=0)break;
for(int i=l;i<=r;i++)
{
a[i-l+1]=b[i];
}
t.init();
t.build(1,1,len);
for(int i=1;i<=m;i++)
{
if(u[i].r<l||r<u[i].l)continue;
ll tl=max(l,u[i].l),tr=min(r,u[i].r);
tl=tl-l+1;tr=tr-l+1;
adt=u[i].v,ans[u[i].i]=ans[u[i].i]+t.query(1,1,len,tl,tr);
}
}
for(int i=1;i<=m;i++)
{
cout<<ans[i].ans<<"\n";
}
}
```
by rrrrr @ 2021-04-28 18:39:25
~~qndmx~~
by qqqqq111 @ 2021-04-28 19:34:40
~~刚学OI代码写如此之长~~
by wyr听取MLE一片 @ 2021-09-04 13:17:15