随便打一打含左端点连续最大值,含右端点连续最大值,以及连续最大字段和就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
#define ll long long 
using namespace std;
const int N=5e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct Seg{ll ls,rs,ms,s;}t[1250005];
ll a[N];
void build(int p,int l,int r)
{
    if(l==r){t[p].ls=t[p].rs=t[p].ms=t[p].s=a[l];return ;}
    int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    t[p].s=t[p<<1].s+t[p<<1|1].s;
    t[p].ls=max(t[p<<1].ls,t[p<<1].s+t[p<<1|1].ls);
    t[p].rs=max(t[p<<1|1].rs,t[p<<1|1].s+t[p<<1].rs);
    t[p].ms=max(t[p<<1].ms,max(t[p<<1|1].ms,t[p<<1].rs+t[p<<1|1].ls));
}
void change(int p,int l,int r,int x,ll d)
{
    if(l==r){t[p].ls=t[p].rs=t[p].ms=t[p].s=d;return ;}
    int mid=l+r>>1;
    if(x<=mid)change(p<<1,l,mid,x,d);
    else change(p<<1|1,mid+1,r,x,d);
    t[p].s=t[p<<1].s+t[p<<1|1].s;
    t[p].ls=max(t[p<<1].ls,t[p<<1].s+t[p<<1|1].ls);
    t[p].rs=max(t[p<<1|1].rs,t[p<<1|1].s+t[p<<1].rs);
    t[p].ms=max(t[p<<1].ms,max(t[p<<1|1].ms,t[p<<1].rs+t[p<<1|1].ls));
}
Seg query(int p,int l,int r,int ql,int qr)
{
    if(ql==l&&qr==r)return t[p];
    int mid=l+r>>1;
    if(qr<=mid)return query(p<<1,l,mid,ql,qr);
    else if(ql>mid)return query(p<<1|1,mid+1,r,ql,qr);
    else
    {
        Seg lc,rc,now;
        lc=query(p<<1,l,mid,ql,mid);
        rc=query(p<<1|1,mid+1,r,mid+1,qr);
        now.s=lc.s+rc.s;
        now.ls=max(lc.ls,lc.s+rc.ls);
        now.rs=max(rc.rs,rc.s+lc.rs);
        now.ms=max(lc.ms,max(rc.ms,lc.rs+rc.ls));
        return now;
    }
}
int main()
{
    int n,m;qr(n);qr(m);
    for(int i=1;i<=n;i++)qr(a[i]);
    build(1,1,n);
    for(int i=1,k,l,r,x;i<=m;i++)
    {
        qr(k);ll d;
        if(k==1){qr(l),qr(r);if(l>r)swap(l,r);qw(query(1,1,n,l,r).ms);puts("");}
        else {qr(x);qr(d);change(1,1,n,x,d);}
    }
    return 0;
}