9pts 有交换 pushup应该没问题

#include<bits/stdc++.h>
#include<stack>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x*f;
}
#define re register

int n,m;
const int inf=0x3f3f3f3f;
const int N=5e5+10;
int a[N];

namespace seg
{
#define ls (rt*2)
#define rs (rt*2+1)
#define mid ((l+r)>>1)
    struct node
    {
        int all_max,sum,left_max,right_max;
    } t[N*4];
    inline void mat(int rt)
    {
        t[rt].sum = t[rs].sum + t[ls].sum;
        t[rt].left_max = max( t[ls].left_max , t[ls].all_max+t[rs].left_max );
        t[rt].right_max = max( t[rs].right_max , t[rs].all_max+t[ls].right_max );
        t[rt].all_max = max( max(t[ls].all_max,t[rs].all_max) , t[rs].left_max + t[ls].right_max );
    }
    inline void build(int rt,int l,int r)
    {
        if(l==r)
        {
            t[rt].all_max=a[l];
            t[rt].left_max=a[l];
            t[rt].right_max=a[l];
            t[rt].sum=a[l];
            return ;
        }
        build(ls,l,mid);
        build(rs,mid+1,r);
        mat(rt);
    }
    inline void modify(int rt,int l,int r,int p,int v)
    {
        if(l==p && r==p)
        {
            t[rt].all_max=v;
            t[rt].left_max=v;
            t[rt].right_max=v;
            t[rt].sum=v;
            return ;
        }
        if(p<=mid)modify(ls,l,mid,p,v);
        else modify(rs,mid+1,r,p,v);
        mat(rt);
    }
    inline node query(int rt,int l,int r,int L,int R)
    {
        if(L<=l && r<=R)
        {
            return t[rt];
        }
        node ans,al,ar;
        ans.sum=0;
        if(R<=mid) ans=query(ls,l,mid,L,R);
        if(L>mid)  ans=query(rs,mid+1,r,L,R);
        if(L<=mid&&mid<R)
        {
            al=query(ls,l,mid,L,R);
            ar=query(rs,mid+1,r,L,R);
            ans.sum=al.sum+ar.sum;
            ans.left_max=max( al.left_max , al.all_max+ar.left_max  );
            ans.right_max=max( ar.right_max , ar.all_max+al.right_max );
            ans.all_max=max( max(al.all_max,ar.all_max),al.right_max+ar.left_max  );
        }
        return ans;
    }
}
int main()
{
    freopen("P4513_2.in","r",stdin);
    freopen("ans.out","w",stdout);
    n=read();
    m=read();
    for(int i=1; i<=n; i++) a[i]=read();
    seg::build(1,1,n);
    while(m--)
    {
        int opt=read();
        if(opt==1)
        {
            int l=read(),r=read();
            if(l>r)swap(l,r);
            seg::node ans=seg::query(1,1,n,l,r);
            cout<< ans.all_max <<endl;
        }
        else
        {
            int p=read(),s=read();
            seg::modify(1,1,n,p,s);
        }
    }
}