P4513 小白逛公园 动态维护最大子段和

题目链接：https://www.luogu.org/problem/P4513

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 500005

#define ll long long

#define ls l,mid,rt<<1

#define rs mid+1,r,rt<<1|1

struct node{

    ll sum,lsum,rsum,msum;

}tr[maxn<<];

ll a[maxn];

inline void pushup(int rt)

{

    tr[rt].sum=tr[rt<<].sum+tr[rt<<|].sum;

    tr[rt].lsum=max(tr[rt<<].lsum,tr[rt<<].sum+tr[rt<<|].lsum);

    tr[rt].rsum=max(tr[rt<<|].rsum,tr[rt<<|].sum+tr[rt<<].rsum);

    tr[rt].msum=max(max(tr[rt<<].msum,tr[rt<<|].msum),tr[rt<<|].lsum+tr[rt<<].rsum);

}

inline void build(int l,int r,int rt)

{

    if(l==r)

    {

        tr[rt].sum=tr[rt].msum=tr[rt].lsum=tr[rt].rsum=a[l];

        return ;

    }

    int mid=l+r>>;

    build(ls);build(rs);

    pushup(rt);

}

inline void update(int L,int c,int l,int r,int rt)

{

    if(l==r)

    {

        tr[rt].sum=tr[rt].msum=tr[rt].lsum=tr[rt].rsum=c;

        return ;

    }

    int mid=l+r>>;

    if(L<=mid)update(L,c,ls);

    else update(L,c,rs);

    pushup(rt);

}

inline node query(int L,int R,int l,int r,int rt)

{

    if(L<=l&&R>=r)return tr[rt];

    int mid=l+r>>;

    if(R<=mid)return query(L,R,ls);

    else if(L>mid)return query(L,R,rs);

    else

    {

        node wl=query(L,R,ls),wr=query(L,R,rs),ans;

        ans.lsum=max(wl.lsum,wl.sum+wr.lsum);

        ans.rsum=max(wr.rsum,wr.sum+wl.rsum);

        ans.msum=max(max(wl.msum,wr.msum),wl.rsum+wr.lsum);

        return ans;

    }

}

int main()

{

    int n,m;

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

    for(int i=;i<=n;i++)

    scanf("%lld",&a[i]);

    build(,n,);

    int op,l,r,x;

    for(int i=;i<=m;i++)

    {

        scanf("%d",&op);

        if(op==)

        {

            scanf("%d%d",&l,&r);

            if(l>r)swap(l,r);

            printf("%lld\n",query(l,r,,n,).msum);

        }

        else

        {

            scanf("%d%d",&l,&x);

            update(l,x,,n,);

        }

    }

    return ;

}