萌新求教

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int tr[N*4];
int lm[N*4],rm[N*4];//更新 左 or 右 端点开始的最大子段和
int maxn[N*4];//更新最大子段和的答案。分三种情况：最大子段只在mid左边，跨过mid，只在mid右边。
int n,m;
int a[N*4];
void pushup(int i)
{
    tr[i]=tr[i<<1]+tr[(i<<1)+1];
    maxn[i]=max(max(maxn[i<<1],maxn[(i<<1)+1]),rm[i<<1]+lm[(i<<1)+1]);
    lm[i]=max(lm[i<<1],tr[i<<1]+lm[(i<<1)+1]);
    rm[i]=max(rm[(i<<1)+1],tr[(i<<1)+1]+rm[(i<<1)]);
    return;
}
void update(int i,int l,int r,int x,int val)
{
    if(l==r)
    {
        tr[i]=val;
        maxn[i]=val;
        lm[i]=val;
        rm[i]=val;
        return;
    }
    int mid=l+r>>1;
    if(mid>=x) update(i<<1,l,mid,x,val);
    else update((i<<1)+1,mid+1,r,x,val);
    pushup(i);
}
void built(int i,int l,int r)
{
    if(l==r)
    {
        tr[i]=a[l];
        maxn[i]=a[l];
        lm[i]=a[l];
        rm[i]=a[l];
        return ;
    }
    int mid=l+r>>1;
    built(i<<1,l,mid);
    built((i<<1)+1,mid+1,r);
    pushup(i);
}
int L,R,sum;
int run(int i,int l,int r,int x,int y)
{
    //cout<<"adasdas"<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
    //if(l==2&&r==2&&x==3&&y==2) system("pause");
    if(l==x&&r==y)
    {
        sum=tr[i];
        L=lm[i];
        r=rm[i];
        return maxn[i];
    }
    int mid=l+r>>1;
    if(mid>=y)
        return run(i<<1,l,mid,x,y);//只在mid右边
    else if(mid<x)
        return run((i<<1)+1,mid+1,r,x,y);//只在mid左边
    else//跨过mid
    {
        int tmp=run(i<<1,l,mid,x,mid);
        int jxx=L,cjr=R,hj=sum;
        int ans=max(tmp,run((i<<1)+1,mid+1,r,mid+1,y));
        ans=max(ans,cjr+L);
        L=max(jxx,hj+L);
        R=max(R,sum+cjr);
        return ans;
        /*
        int jxx=L,cjr=R,hj=sum;
        int ans=max(run(i<<1,l,mid,x,mid),run((i<<1)+1,mid+1,r,mid+1,y));
        ans=max(ans,cjr+L);
        L=max(jxx,hj+L);
        R=max(R,sum+cjr);
        return ans;
        */
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        cin>>a[i];
        //build(1,1,n,i,x);
    built(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int x,y,op;
        cin>>op>>x>>y;
        if(op==1)
        {
            if(x>y) swap(x,y);
            cout<<run(1,1,n,x,y)<<endl;
        }
        if(op==2)
        {
            update(1,1,n,x,y);
        }
    }
    return 0;
}