你能回答这些问题吗

AcWing-245-你能回答这些问题吗

分析

见《进阶指南》第215页。

区间最大连续子段和。

分治法求最大连续子段和：

• 左子区间；
• 右子区间；
• 左子区间+右子区间。

实现

#include <iostream>
#define inf (1LL << 60)
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;

typedef long long LL;
const int N = 500010;
struct info {
    LL sum, L, R, A;
};
struct node {
    int l, r;
    info data;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define data(x) t[x].data
    #define sum(x) t[x].data.sum
    #define L(x) t[x].data.L
    #define R(x) t[x].data.R
    #define A(x) t[x].data.A
};
int a[N];
node t[N << 2];

void update (int rt) {
    sum(rt) = sum(ls) + sum(rs);
    L(rt) = max(L(ls), sum(ls) + L(rs));
    R(rt) = max(R(ls) + sum(rs), R(rs));
    A(rt) = max(R(ls) + L(rs), max(A(ls), A(rs)));
}
void build (int rt, int l, int r) {
    l(rt) = l, r(rt) = r;
    if (l == r) {
        data(rt) = { a[l], a[l], a[l], a[l] };
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(rt);
}
void modify (int rt, int idx, int val) { // a[idx] = val
    if (l(rt) == r(rt)) {
        data(rt) = { val, val, val, val };
        return;
    }
    int mid = l(rt) + r(rt) >> 1;
    modify(idx <= mid ? ls : rs, idx, val);
    update(rt);
}
info query (int rt, int l, int r) {
    if (l <= l(rt) && r(rt) <= r) return data(rt);
    int mid = l(rt) + r(rt) >> 1;
    info a, b;
    a = b = { 0, -inf, -inf, -inf };
    if (l <= mid) a = query(ls, l, r);
    if (r >= mid + 1) b = query(rs, l, r);
    return {
        a.sum + b.sum,
        max(a.L, a.sum + b.L),
        max(a.R + b.sum, b.R),
        max(a.R + b.L, max(a.A, b.A)),
    };
}

int main () {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    build(1, 1, n);
    while (m --) {
        int opt;
        scanf("%d", &opt);
        if (opt == 2) {
            int idx, val;
            scanf("%d%d", &idx, &val);
            modify(1, idx, val);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            if (l > r) swap(l, r);
            printf("%lld\n", query(1, l, r).A);
        }
    }
    return 0;
}