线段树9分求救

#include <iostream>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<math.h>
#include <algorithm>
#include<string>
#include<cstring>
#include<list>
#include<stack>

using namespace std;
const int N = 5e5 + 9;
struct han {
    int l, r;
    int sum;
    int lmax;
    int rmax;
    int max;
}h[N*4];
int a[N];
int n, m;

void pushup(int p) {
    h[p].sum = h[p << 1].sum + h[p << 1 | 1].sum;//sum

    int l = h[p << 1].rmax + h[p << 1 | 1].lmax;//zhongjian 

    h[p].lmax = max(h[p<<1].lmax, h[p << 1].sum + h[p << 1 | 1].lmax);

    h[p].rmax = max(h[p << 1 | 1].rmax, h[p << 1].rmax + h[p << 1 | 1].sum);

    l = max(l, h[p << 1].max);
    l = max(l, h[p << 1 | 1].max);
    l = max(l, h[p].lmax);
    l = max(l, h[p].rmax);

    h[p].max = l;
}

void wdy_cr(int p, int x, int y) {
    h[p] = { x,y,a[x],a[x],a[x],a[x]};
    if (x == y)return;
    int mid = x + y >> 1;
    wdy_cr(p << 1, x, mid);
    wdy_cr(p << 1 | 1, mid + 1, y);
    pushup(p);
}

void wdy_qu(int p, int x, int z) {
    if (x == h[p].l && x == h[p].r) {
        h[p].sum = z;
        h[p].lmax = z;
        h[p].rmax = z;
        h[p].max = z;
        return;
    }
    int mid = h[p].l + h[p].r >> 1;
    if (x <= mid)wdy_qu(p << 1, x, z);
    if (x > mid)wdy_qu(p << 1 | 1, x, z);
    pushup(p);
}

han wdy_cha(int p, int x, int y) {
    if (x <= h[p].l && y >= h[p].r) {
        return h[p];
    }
    int mid = h[p].l + h[p].r >> 1;

    if (y<=mid)return wdy_cha(p << 1, x, y);
    if (x>mid)return wdy_cha(p << 1 | 1, x, y);

    han h1 = wdy_cha(p << 1, x, y);
    han h2 = wdy_cha(p << 1 | 1, x, y);
    han hh={0,0,0,0,0,0};

    hh.sum = h1.sum + h2.sum;
    int l = h1.rmax + h2.lmax;

    hh.lmax = (h1.lmax, h1.sum + h2.lmax);
    hh.rmax = (h2.rmax, h2.sum + h1.rmax);

    l = max(l, h1.max);
    l = max(l, h2.max);
    l = max(l, hh.lmax);
    l = max(l, hh.rmax);
    hh.max = l;
    return hh;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    wdy_cr(1, 1, n);
    int op, x, y;

    for (int i = 1; i <= m; i++) {
        cin >> op >> x >> y;
        if (op == 1) {
            if (x > y)swap(x, y);
            han h = wdy_cha(1,x, y);
            cout << h.max << endl;

        }
        else {
            wdy_qu(1, x, y);
        }
    }
    return 0;
}