分块

块内需要维护前缀后缀全局的最大子段和

前缀后缀的求个凸包就行了

全局的话,每次求出当前最大子段和及长度,并求出使长度变化全局至少要加多少

因为加的是正数,所以一旦变化长度一定是变长的

所以只会变$n$次

求这个可以直接二分,但是是$\log{值域}$的

更好的方法是考虑以$i$为右端点时,就是要求$\min{(ans_{s}-(s_{i}-s_{j}))/((i-j)-ans_{len})}$,其中$j < i-ans_{len}$

所以可以从左到右枚举$i$,维护$(j,-s_{j})$的凸包,然后在凸包上二分.

时间$O(n \sqrt{n \log{n} })$

但是其实还有一个问题,就是当加在一个块的一个部分时,其答案长度可能变短

这样时间就没法证了..

我既不会证也不会卡,只能求出大佬了..

(其实我向$lxl$要了题解..但感觉太麻烦了而且常数大就写了这个)

(如果能有人优化下面代码或者自己写一个然后打败标算也是极好的)

(其实这个代码是很难过的,我在$luogu$上试了十几个分块长度才过的,不过一过就踩了标算.)

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define mid (l+r>>1)

template <typename T> inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

const int ch_top=6e6;
char ch[ch_top],*now_r=ch-1;
char ch_w[ch_top],*now_w=ch_w-1;
#define gc (*++now_r)
#define c (*now_r)
int read()
{
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
int readz()
{
    while(gc<'-');
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
#undef c
void write(ll &ans)
{
    if(ans<10){*++now_w='0'+ans;*++now_w='\n';return ;}
    static char st[20];
    int top=0;
    do{st[++top]='0'+ans%10;}while(ans/=10);
    do{*++now_w=st[top];}while(--top);
    *++now_w='\n';
}

#define B(x) ((x-1)/L)
const int N=1e5+5,L=/*4*/192,K=N/L+5;
const ll inf=1e11+2e9+1;
int n;
ll a[N];
struct TU
{
int q[L];ll s[L];
int head,tail;
};
struct BLOCK
{
int l,r;
ll ans;int anslen;ll nex;
ll ad;
TU pre,suf;ll sum;
bool full;
};
BLOCK block[K],*b,*e,*belong[N];

namespace BUILD
{
ll a[L];
ll ns[L];int nq[L];
ll ans;int anslen;
bool ok(const ll &x)
{
    ll s=0,li=ans+anslen*x;
    rep(i,0,L-1)
    {
        s=(s+a[i]+x<0)?0:s+a[i]+x;
        if(s>li)return 1;
    }

    return 0;
}
void build(BLOCK &k,bool init=1)
{
    ll x=k.ad,*_a=::a+k.l;
    k.ad=0;
    rep(i,0,L-1)a[i]=(_a[i]+=x);
    ll s;
   ans=0;anslen=0;
    s=0;int len=0;
    rep(i,0,L-1)
    {
        s+=a[i];
        if(s<0){s=0;len=0;}
        else
        {
            ++len;
            if(s>ans){ans=s;anslen=len;}
            else
            if(s==ans&&len>anslen)anslen=len;
        }
    }
    k.ans=ans;k.anslen=anslen;

    if(/*!ok(inf)*/anslen==L){k.nex=inf;k.pre.head=k.suf.head=k.pre.tail=k.suf.tail=0;k.pre.s[0]=k.suf.s[0]=k.sum=ans;k.full=1;return ;}
if(init)
{
    int /*head=0,*/tail=-1;
    ll *ns=k.pre.s;int *nq=k.pre.q;
    s=0;
    rep(i,1,L)
    {
        s+=a[i-1];
        while(tail>=0&&ns[tail]<=s)--tail;
        while(tail>=1&&(nq[tail-1]-i)*(ns[tail]-s)>=(nq[tail]-i)*(ns[tail-1]-s))--tail;
        ++tail;
        nq[tail]=i;ns[tail]=s;
    }
    k.pre.head=/*head*/0;k.pre.tail=tail;
    k.sum=s;

    /*head=0;*/tail=-1;
    ns=k.suf.s;nq=k.suf.q;
    s=0;
    rep(i,1,L)
    {
        s+=a[L-i];
        while(tail>=0&&ns[tail]<=s)--tail;
        while(tail>=1&&(nq[tail-1]-i)*(ns[tail]-s)>=(nq[tail]-i)*(ns[tail-1]-s))--tail;
        ++tail;
        nq[tail]=i;ns[tail]=s;
    }
    k.suf.head=/*head*/0;k.suf.tail=tail;
}
else
{
    ll *ns=k.pre.s;int *nq=k.pre.q;
    int i=k.pre.tail,head=k.pre.head;
    ns[i]+=x*nq[i];
    k.sum=ns[i];
    while(--i>=head)
    {
        ns[i]+=x*nq[i];
        if(ns[i]<=ns[i+1]){k.pre.head=i+1;break;}
    }


    ns=k.suf.s;nq=k.suf.q;
    i=k.suf.tail;head=k.suf.head;
    ns[i]+=x*nq[i];
    while(--i>=head)
    {
        ns[i]+=x*nq[i];
        if(ns[i]<=ns[i+1]){k.suf.head=i+1;break;}
    }
}
/*  ll l=0,r=10000;
    while(!ok(r)){r<<=1;if(r>=inf){r=inf;break;}}
    while(l+1!=r)
    if(ok(mid))r=mid;
    else l=mid;
    k.nex=r;*/
    ll nex=inf;
static bool may[L];
    s=0;
    per(i,L-1,anslen)
    {
        may[i]=s<=0;
        s=s+a[i]<0?0:s+a[i];
    }

    s=0;ll y=ans;
    int top=0;
    ns[0]=0;nq[0]=-1;
    int i=anslen,j=0;
    rep(k,0,i-1)y-=a[k];
    while(i<L)
    {
        s-=a[j];y-=a[i];

        if(may[i])
        {   
        //int x=i-anslen;
#define x j
        if(top<5)
        {
            rep(h,0,top)
            if((x-nq[h])*nex>y-ns[h])nex=(y-ns[h])/(x-nq[h]);
        }
        else
        {
            int l=0,r=top;
            while(l!=r)
            if((nq[mid+1]-x)*(ns[mid]-y)>=(nq[mid]-x)*(ns[mid+1]-y))l=mid+1;
            else r=mid;

            if((x-nq[l])*nex>y-ns[l])nex=(y-ns[l])/(x-nq[l]);
        }
#undef x
        }

        while(top>=1&&(nq[top-1]-j)*(ns[top]-s)>=(nq[top]-j)*(ns[top-1]-s))--top;
        if(s>ns[top]){ns[++top]=s;nq[top]=j;}
        ++i;++j;
    }

    k.nex=ok(nex)?nex:nex+1;
//  printf("%lld\n",k.nex);
}
};
using BUILD::build;

int main()
{
//  freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    ch[fread(ch,1,ch_top,stdin)]=0;
    n=readz();int m=readz();
    rep(i,1,n)a[i]=read();
    b=block;e=b-1;
    for(int l=1;l<=n;)
    {
        int r=l+L-1;
        if(l==1)r=l+L*2; 
        if(l+L*2>=n)r=n;
        ++e;
        e->l=l;e->r=r;
        while(l<=r){belong[l]=e;++l;}
    }
    for(BLOCK *p=b+1;p<e;++p)build(*p);
    while(m--)
    {
        while(gc<'0');
        if(*now_r=='1')
        {
            int l=readz(),r=readz(),x=readz();
            BLOCK *bl=belong[l],*br=belong[r];
            if(bl==br)
            {
                rep(i,l,r)a[i]+=x;
                if(bl>b&&bl<e)
                {
                    if(bl->full)bl->ans+=(ll)x*(r-l+1);
                    else build(*bl);
                }
            }
            else
            {
                int bl_r=bl->r;
                rep(i,l,bl_r)a[i]+=x;
                if(bl>b)
                {
                    if(bl->full)bl->ans+=(ll)x*(bl_r-l+1);
                    else build(*bl);
                }

                while(++bl<br)bl->ad+=x;

                int br_l=br->l;
                rep(i,br_l,r)a[i]+=x;
                if(br<e)
                {
                    if(br->full)br->ans+=(ll)x*(r-br_l+1);
                    else build(*br);
                }
            }
        }
        else
        {
            int l=readz(),r=readz();
        //  if(r-l<=L*2)
            if(belong[l]==belong[r])
            {   
                ll ans=0,s=0,x=belong[l]->ad;
                rep(i,l,r)
                {
                    s=(s+a[i]+x<0)?0:s+a[i]+x;
                    if(s>ans)ans=s;
                }
                write(ans);
                continue;
            }
            ll ans=0,s=0;
            BLOCK *bl=belong[l],*br=belong[r];
            int bl_r=bl->r;ll x=bl->ad;
            rep(i,l,bl_r)
            {
                s=(s+a[i]+x<0)?0:s+a[i]+x;
                if(s>ans)ans=s;
            }
            while(++bl<br)
            {
                x=bl->ad;
                if(bl->full)
                {
                    s+=bl->ans+x*L;
                    if(s>ans)ans=s;
                }
                else
                if(x>=bl->nex)
                {
                    build(*bl,0);
                    if(bl->ans>ans)ans=bl->ans;
                    if(s+bl->pre.s[bl->pre.head]>ans)ans=s+bl->pre.s[bl->pre.head];
                    s=max(0LL,max(s+bl->sum,bl->suf.s[bl->suf.head]));
                }
                else
                {
                    if(bl->ans+x*bl->anslen>ans)ans=bl->ans+x*bl->anslen;
                #define get q->s[q->head]+x*q->q[q->head]
                #define pop while(q->head<q->tail&&q->s[q->head]<q->s[q->head+1]+x*(q->q[q->head+1]-q->q[q->head]))++q->head;
                    TU *q=&bl->pre;
                    pop
                    if(s+get>ans)ans=s+get;
                    q=&bl->suf;
                    pop
                    s=max(0LL,max(s+bl->sum+x*L,get));
                #undef get
                #undef pop
                }
            }
            int br_l=br->l;x=br->ad;
            rep(i,br_l,r)
            {
                s=(s+a[i]+x<0)?0:s+a[i]+x;
                if(s>ans)ans=s;
            }
            write(ans);
        }
    }
    fwrite(ch_w,1,now_w-ch_w+1,stdout);
}