秋条，8pts。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m;
const int N=5e5+5;
int op,x,y;
int a[N];
int treel[N<<2],treer[N<<2],treemax[N<<2],tree[N<<2];
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
struct node
{
    int sum,l,r,max;
};
void push_up(int p)
{
    treemax[p]=treel[rs(p)]+treer[ls(p)];
    treemax[p]=max(treemax[p],max(treemax[ls(p)],treemax[rs(p)]));
    tree[p]=tree[ls(p)]+tree[rs(p)];
    treel[p]=max(treel[ls(p)],tree[ls(p)]+treel[rs(p)]);
    treer[p]=max(treer[rs(p)],tree[rs(p)]+treer[ls(p)]);
}
void build(int s,int t,int p)
{
    if(s==t)
    {
        treel[p]=treer[p]=tree[p]=treemax[p]=a[s];
        return;
    }
    int mid=s+((t-s)>>1);
    build(s,mid,ls(p));
    build(mid+1,t,rs(p));
    push_up(p);
}
void update(int x,int k,int s,int t,int p)
{
    if(s==t)
    {
        treel[p]=treer[p]=tree[p]=treemax[p]=k;
        return;
    }
    int mid=s+((t-s)>>1);
    if(x<=mid) update(x,k,s,mid,ls(p));
    else update(s,k,mid+1,t,rs(p));
    push_up(p);
}
node query(int l,int r,int s,int t,int p)
{
    if(l<=s and t<=r) return (node){tree[p],treel[p],treer[p],treemax[p]};
    int mid=s+((t-s)>>1);
    node ansl={(int)-1e9,(int)-1e9,(int)-1e9,(int)-1e9},ansr={(int)-1e9,(int)-1e9,(int)-1e9,(int)-1e9},ans;
    if(l<=mid) ansl=query(l,r,s,mid,ls(p));
    if(mid+1<=r) ansr=query(l,r,mid+1,t,rs(p));
    ans.max=max(ansl.r+ansr.l,max(ansl.max,ansr.max));
    ans.sum=ansl.sum+ansr.sum;
    ans.l=max(ansl.l,ansl.sum+ansr.l);
    ans.r=max(ansr.r,ansr.sum+ansl.r);
    return ans;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,n,1);
    while(m--)
    {
        cin>>op>>x>>y;
        if(op==1) cout<<query(min(x,y),max(x,y),1,n,1).max<<'\n';
        else update(x,y,1,n,1);
        //for(int i=1;i<=n*4;i++) cout<<treemax[i]<<' ';
        //cout<<'\n';
    }
    return 0;
}