P4513 小白逛公园

单点修改，区间查询最大连续子段和

#include<iostream>
#include<cstdio>
#define ls(x) x<<1
#define rs(x) x<<1|1

using namespace std;

struct Node{
    int sum,lmax,rmax,ans;
}t[2000010];
int n,m,a[500010];
void push_up(int p){//传递信息
    t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
    t[p].lmax = max(t[ls(p)].lmax,t[ls(p)].sum+t[rs(p)].lmax);
    t[p].rmax = max(t[rs(p)].rmax,t[rs(p)].sum+t[ls(p)].rmax);
    t[p].ans = max(max(t[ls(p)].ans,t[rs(p)].ans),t[ls(p)].rmax+t[rs(p)].lmax);
}
void build(int p,int l,int r){//建树
    if(l == r){
        t[p].sum = t[p].lmax = t[p].rmax = t[p].ans = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void modify(int p,int l,int r,int x,int k){//修改 p为当前节点 l r为当前节点维护区间，将x位置的数修改为k
    if(l == r){
        t[p].sum = t[p].lmax = t[p].rmax = t[p].ans = k;
        return ;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)modify(ls(p),l,mid,x,k);
    else modify(rs(p),mid+1,r,x,k);
    push_up(p);
}
Node query(int p,int l,int r,int ql,int qr){//查询 p l r意义同modify ql qr为查询区间
    if(ql <= l && qr >= r)return t[p];//如果完全覆盖直接返回
    int mid = (l + r) >> 1;
    if(ql <= mid && mid < qr){//覆盖左右两个儿子 用pushup的方法将其“合并”
        Node temp,tls = query(ls(p),l,mid,ql,qr),trs = query(rs(p),mid+1,r,ql,qr);
        temp.sum = tls.sum + trs.sum;
        temp.lmax = max(tls.lmax,tls.sum+trs.lmax);
        temp.rmax = max(tls.rmax,trs.sum+tls.rmax);
        temp.ans = max(max(tls.ans,trs.ans),tls.rmax+trs.lmax);
        return temp;
    }
    else if(ql <= mid)return query(ls(p),l,mid,ql,qr);//只覆盖左儿子
    else return query(rs(p),mid+1,r,ql,qr);//只覆盖右儿子
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; i ++)scanf("%d",&a[i]);
    build(1,1,n);
    int k,a,b;
    while(m--){
        scanf("%d%d%d",&k,&a,&b);
        if(k == 1){
            if(a > b)swap(a,b);
            printf("%d\n",query(1,1,n,a,b).ans);
        }
        else{
            modify(1,1,n,a,b);
        }
    }
    return 0;
}