9ptsRE本地能过求调

#include <bits/stdc++.h>

using namespace std;
#define ls u << 1
#define rs u << 1 | 1
const int maxn = 5e5 + 5;
struct line {
    int l, r, sum, lmax, rmax, ans;
} t[maxn << 2];
int val[maxn];

line push_up(line l, line r) {
    line res;
    res.sum = l.sum + r.sum;
    res.lmax = max(l.lmax, l.sum + r.lmax);
    res.rmax = max(r.rmax, r.sum + l.rmax);
    res.ans = max({l.ans, r.ans, l.rmax + r.lmax});
    res.l = l.l;
    res.r = r.r;
    return res;
}

void build(int u, int l, int r) {
    if (l == r) {
        t[u].l = l;
        t[u].r = r;
        t[u].ans = t[u].sum = t[u].lmax = t[u].rmax = val[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    t[u] = push_up(t[ls], t[rs]);
}

void modify(int u, int x, int v) {
    if (t[u].l == x && x == t[u].r) {
        t[u].ans = t[u].sum = t[u].lmax = t[u].rmax = v;
        return;
    }
    int mid = (t[u].l + t[u].r) >> 1;
    if (x <= mid) {
        modify(ls, x, v);
    } else {
        modify(rs, x, v);
    }
    t[u] = push_up(t[ls], t[rs]);
}

line query(int u, int l, int r) {
    if (l <= t[u].l && r >= t[u].r) {
        return t[u];
    }
    int mid = (t[u].l + t[u].r) >> 1;
    if (l > mid) {
        return query(rs, l, r);
    }
    if (r <= mid) {
        return query(ls, l, r);
    }
    return push_up(query(ls, l, r), query(rs, l, r));
}

void best_coder() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int opt, l, r;
        cin >> opt >> l >> r;
        if (opt == 1) {
            if (l > r) {
                swap(l, r);
            }
            cout << query(1, l, r).ans << "\n";
        } else {
            modify(1, l, r);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    best_coder();

    return 0;
}