题意：

单点修改，区间最值

思路：

线段树

原题请戳这里

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

#define LSON l,mid,lson

#define RSON mid+1,r,rson

#define N 500000

#define inf 0x3fffffff

using namespace std;

int n,m,jy,xx,yy,RANS,ANS;

int tree[N*4],lmax[N*4],rmax[N*4],maxx[N*4],sum[N*4];

void push_up(int pos,int lson,int rson){

    sum[pos]=sum[lson]+sum[rson];

    rmax[pos]=max(rmax[rson],sum[rson]+rmax[lson]);

    lmax[pos]=max(lmax[lson],lmax[rson]+sum[lson]);

    maxx[pos]=max(maxx[lson],max(maxx[rson],rmax[lson]+lmax[rson]));

}

void build(int l,int r,int pos){

    if(l==r){

        scanf("%d",&tree[pos]);

        lmax[pos]=rmax[pos]=sum[pos]=maxx[pos]=tree[pos];

        return;

    }

    int mid=(l+r)/2,lson=pos<<1,rson=pos<<1|1;

    build(LSON);build(RSON);

    push_up(pos,lson,rson);

}

void query(int l,int r,int pos){

    if(l>=xx&&r<=yy){

        ANS=max(ANS,max(maxx[pos],RANS+lmax[pos]));

        RANS=max(rmax[pos],RANS+sum[pos]);

        return;

    }

    int mid=(l+r)/2,lson=pos<<1,rson=pos<<1|1;

    if(mid<xx)query(RSON);

    else if(mid>=yy)query(LSON);

    else query(LSON),query(RSON);

}

void update(int l,int r,int pos){

    if(l==r){

        lmax[pos]=rmax[pos]=sum[pos]=maxx[pos]=tree[pos]=yy;

        return;

    }

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(mid<xx)update(RSON);

    else update(LSON);

    push_up(pos,lson,rson);

}

int main(){

    scanf("%d%d",&n,&m);

    build(1,n,1);

    while(m--){

        scanf("%d%d%d",&jy,&xx,&yy);

        if(jy==1){

            if(xx>yy)swap(xx,yy);

            ANS=RANS=-inf;

            query(1,n,1);

            printf("%d\n",ANS);

        }

        else

            update(1,n,1);

    }

}