2 - #11 WA

求调……

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct node{
    int l, r, sum, val, lv, rv;
}tree[500005 * 4];

int a[500005];

void pushup(int id){
    tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum; 
    tree[id].val = max(tree[id * 2].val, max(tree[id * 2 + 1].val, tree[id * 2].rv + tree[id * 2 + 1].lv));
    tree[id].lv = max(tree[id * 2].lv, tree[id * 2 + 1].lv + tree[id * 2].sum);
    tree[id].rv = max(tree[id * 2].rv, tree[id * 2 + 1].rv + tree[id * 2].sum);
}

void build(int id, int l, int r){
    tree[id].l = l;
    tree[id].r = r;
    if(l == r){
        tree[id].sum = a[l];
        tree[id].val = a[l];
        tree[id].lv = a[l];
        tree[id].rv = a[l];
    }
    else{
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        pushup(id);
    }
}

node query(int id, int l, int r){
    if(tree[id].l >= l && tree[id].r <= r){
        return tree[id];
    }
    node a, b, ans;
    a.lv = a.rv = a.val = -1e9;
    b.lv = b.rv = b.val = -1e9;
    ans.val = -1e9;
    int mid = (tree[id].l + tree[id].r) / 2;
    a.sum = b.sum = ans.sum = 0;
    if(l <= mid){
        a = query(id * 2, l, r);
        ans.sum += a.sum;
    }
    if(r > mid){
        b = query(id * 2 + 1, l, r);
        ans.sum += b.sum;
    }
    ans.val = max(a.val, max(b.val, a.rv + b.lv));
    ans.lv = max(a.lv, b.lv + a.sum);
    ans.rv = max(a.rv, a.rv + b.sum);
    if(l > mid){
        ans.lv = max(ans.lv, b.lv);
    }
    if(r < mid){
        ans.rv = max(ans.rv, a.rv);
    }
    return ans;
}

void update(int id, int x, int v){
    if(tree[id].l == x && tree[id].r == x){
        tree[id].sum = tree[id].lv = tree[id].rv = tree[id].val = v;
    }
    else{
        int mid = (tree[id].l + tree[id].r) / 2;
        if(x <= mid) update(id * 2, x, v);
        else update(id * 2 + 1, x, v);
        pushup(id);
    }
}

signed main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    build(1, 1, n);
    while(m--){
        int op;
        cin >> op;
        if(op == 1){
            int l, r;
            cin >> l >> r;
            if(l > r){
                swap(l, r);
            }
            node a = query(1, l, r);
            cout << a.val << endl;
        }
        else{
            int x, k;
            cin >> x >> k;
            update(1, x, k);
        }
    }
    return 0;
}