不知道博客能不能写题解，我来试试。

一道版蓝。

P4513

题目大意

现在有两种操作：

1. 输出区间为 a,b 的最大子段和
2. 将第 p 个公园的打分变为 s

思路

我们知道本题需要在区间和线段树的前提下维护最大子段和。我们发现某区间的最大值有以下三种情况

1. 全部位于左孩子
2. 全部位于右孩子
3. 两边都有

那么我们可以在线段树结构体的基础上再开三个变量，即从左边开始的最大子段和，从右边开始的最大子段和，整个区间的最大子段和。那么代码易得。注意我们要把懒标记扔进旁边的垃圾桶。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=4000005;
vector<int> a(N);
class segment_tree{
    private:
        struct node{
            int data,l,r,maxx;
        }tree[N];
        int left_child(int now){//取左孩子，返回的是索引
            return 2*now;
        }int right_child(int now){//取右孩子
            return 2*now+1;
        }void pushup(int now){//这里方便一点写了一个 pushup
            tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
            tree[now].maxx=max(tree[left_child(now)].maxx,max(tree[left_child(now)].r+tree[right_child(now)].l,tree[right_child(now)].maxx));
            tree[now].l=max(tree[left_child(now)].l,tree[left_child(now)].data+tree[right_child(now)].l);
            tree[now].r=max(tree[right_child(now)].r,tree[right_child(now)].data+tree[left_child(now)].r);
        }
    public:
        void build(int now,int l,int r){//递归建树
            if(l==r){//叶子节点
                tree[now].data=tree[now].l=tree[now].r=tree[now].maxx=a[l];
                return ;
            }int mid=l+(r-l)/2;
            build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
            pushup(now);
        }
        node query_add(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
            if(ql<=l and qr>=r)return tree[now];
            int mid=l+(r-l)/2;
            node ml,mr,ans;
            if(qr<=mid)return query_add(left_child(now),l,mid,ql,qr);
            if(ql>mid)return query_add(right_child(now),mid+1,r,ql,qr);
            ml=query_add(left_child(now),l,mid,ql,qr);
            mr=query_add(right_child(now),mid+1,r,ql,qr);
            ans.data=ml.data+mr.data;
            ans.maxx=max(ml.maxx,max(mr.maxx,ml.r+mr.l));
            ans.l=max(ml.l,ml.data+mr.l);
            ans.r=max(mr.r,mr.data+ml.r);
            return ans;
        }
        void update(int now,int l,int r,int idx,int val){//单点更新
            if(l==r){
                tree[now]={val,val,val,val};
                return ;
            }int mid=l+(r-l)/2;
            if(mid>=idx){
                update(left_child(now),l,mid,idx,val);
            }else{
                update(right_child(now),mid+1,r,idx,val);
            }pushup(now);
        }
};
signed main(){
    segment_tree tree;
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }tree.build(1,1,n);
    while(m--){
        int op,x,y;
        cin >> op;
        cin >> x >> y; 
        
        if(op==1){
            if(x>y)swap(x,y);
            cout << tree.query_add(1,1,n,x,y).maxx << endl;
        }
        else tree.update(1,1,n,x,y);
    }
    return 0;
}