6

标签： get int mid LS lp inf

#include <bits/stdc++.h>

#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 2e6 + 10;

inline int read() {
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
    int res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

int sum[N << 2], sumL[N << 2], sumR[N << 2], maxSum[N << 2], a[N];

inline int ls(int p) { return p << 1; }

inline int rs(int p) { return p << 1 | 1; }

void pushup(int p) {
    sum[p] = sum[ls(p)] + sum[rs(p)];
    sumR[p] = max(sumR[rs(p)], sumR[ls(p)] + sum[rs(p)]);
    sumL[p] = max(sumL[ls(p)], sum[ls(p)] + sumL[rs(p)]);
    maxSum[p] = max(max(maxSum[ls(p)], maxSum[rs(p)]), sumR[ls(p)] + sumL[rs(p)]);
}

void build(int p, int l, int r) {
    if (l == r) {
        sum[p] = sumL[p] = sumR[p] = maxSum[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    pushup(p);
}

void update(int p, int lp, int rp, int pos, int k) {
    if (lp == rp && lp == pos) {
        sum[p] = sumL[p] = sumR[p] = maxSum[p] = k;
        return;
    }
    int mid = (lp + rp) >> 1;
    if (pos <= mid) update(ls(p), lp, mid, pos, k);
    else update(rs(p), mid + 1, rp, pos, k);
    pushup(p);
}

tuple<int, int, int, int> query(int p, int lp, int rp, int l, int r) {
    if (lp >= l && rp <= r) return make_tuple(maxSum[p], sum[p], sumL[p], sumR[p]);
    int mid = (lp + rp) >> 1;
    tuple<int, int, int, int> LS(-inf, -inf, -inf, -inf), RS(-inf, -inf, -inf, -inf), ans(-inf, -inf, -inf, -inf);
    if (r <= mid) return query(ls(p), lp, mid, l, r);
    if (l > mid) return query(rs(p), mid + 1, rp, l, r);
    LS = query(ls(p), lp, mid, l, r);
    RS = query(rs(p), mid + 1, rp, l, r);
    get<0>(ans) = max(max(get<0>(LS), get<0>(RS)), get<3>(LS) + get<2>(LS));
    get<1>(ans) = get<1>(LS) + get<1>(RS);
    get<2>(ans) = max(get<2>(LS), get<1>(LS) + get<2>(RS));
    get<3>(ans) = max(get<3>(RS), get<3>(LS) + get<1>(RS));
    return ans;
}

signed main() {
    //freopen("P1253_5.in", "r", stdin);
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    build(1, 1, n);
    while (m--) {
        int opt = read();
        if (opt == 1) {
            int l = read(), r = read();
            if(r<l) swap(l,r);
            printf("%lld\n", get<0>(query(1, 1, n, l, r)));
        } else {
            int p = read(), s = read();
            update(1, 1, n, p, s);
        }
    }
    return 0;
}

标签：,get,int,mid,LS,lp,inf
From： https://www.cnblogs.com/Jefferyz/p/18117739