70 分做法 && std

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 200010;

typedef long long ll;

struct Tree
{
    ll s, ls, rs, ms;
} tr[N * 4];

void pushup(int u) {
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
    tr[u].ls = max(tr[u << 1].ls, tr[u << 1].s + tr[u << 1 | 1].ls);
    tr[u].rs = max(tr[u << 1].rs + tr[u << 1 | 1].s, tr[u << 1 | 1].rs);
    tr[u].ms = max(max(tr[u << 1].ms, tr[u << 1 | 1].ms), tr[u << 1].rs + tr[u << 1 | 1].ls);
}

void modify(int u, int l, int r, int x, int v) {
    if (l == r) tr[u].s = tr[u].ls = tr[u].rs = tr[u].ms = v;
    else {
        int mid = l + r >> 1;
        if (x <= mid) modify(u << 1, l, mid, x, v);
        else modify(u << 1 | 1, mid + 1, r, x, v);
        pushup(u);
    }
}

Tree query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[u];
    else {
        int mid = l + r >> 1;
        Tree lt, rt;
        bool lv = false, rv = false;
        if (ql <= mid) {
            lv = true;
            lt = query(u << 1, l, mid, ql, qr);
        }
        if (qr > mid) {
            rv = true;
            rt = query(u << 1 | 1, mid + 1, r, ql, qr);
        }
        if (lv && rv) {
            return {lt.s + rt.s, max(lt.ls, lt.s + rt.ls), max(lt.rs + rt.s, rt.rs), max(max(lt.ms, rt.ms), lt.rs + rt.ls)};
        }
        else if (lv) {
            return lt;
        }
        else {
            return rt;
        }
    }
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        int t;
        scanf("%d", &t);
        modify(1, 1, n, i, t);
    }
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", query(1, 1, n, l, r).ms);
    }
    return 0;
}

#include <cstdio>
#include <cmath>
#include <iostream>

typedef long long ll;

namespace Reader {
    char buf[1 << 20], *p1, *p2;

    char gc() {
        if (p1 == p2) p1 = buf, p2 = buf + fread(buf, 1, 1 << 20, stdin);
        return p1 == p2 ? EOF : *p1++;
    }

    inline ll read() {
        ll x = 0, f = 1;
        char c = gc();
        while (!isdigit(c)) {
            if (c == '-') f = -1;
            c = gc();
        }
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
        return x * f;
    }
}

namespace Writer {
    char buf[1 << 10], *p1, *p2;

    void init() {
        p1 = buf, p2 = buf + (1 << 10);
    }

    void flush() {
        fwrite(buf, 1, p1 - buf, stdout);
        p1 = buf;
    }

    void pc(const char c) {
        if (p1 == p2) flush();
        *p1++ = c;
    }

    void pnum(const ll x) {
        if (x < 10) pc(x + 48);
        else pnum(x / 10), pc(x % 10 + 48);
    }

    void write(const ll x, const char c) {
        if (x < 0) pc('-'), pnum(-x), pc(c);
        else pnum(x), pc(c);
    }
}

struct FastIO
{
    FastIO() {
        Writer::init();
    }
} IO;

const int N = 400010;

using namespace Reader;
using namespace Writer;
using namespace std;

struct Tree
{
    ll sum, lsum, rsum, subsum;
} tr[20][N];
int a[N], p[N];
int logn[N * 4];

void init(int n) {
    n <<= 2;
    for (int i = 2; i <= n; ++i) {
        logn[i] = logn[i >> 1] + 1;
    }
}

Tree new_node(int val) {
    return (Tree){val, val, val, val};
}

Tree merge(Tree t1, Tree t2) {
    return {t1.sum + t2.sum, max(t1.lsum, t1.sum + t2.lsum), max(t1.rsum + t2.sum, t2.rsum), max(max(t1.subsum, t2.subsum), t1.rsum + t2.lsum)};
}

void build(int u, int l, int r, int d) {
    if (l == r) p[l] = u, tr[d][l] = new_node(a[l]);
    else {
        int mid = l + r >> 1;
        tr[d][mid] = new_node(a[mid]);
        for (int i = mid - 1; i >= l; --i) {
            tr[d][i] = merge(new_node(a[i]), tr[d][i + 1]);
        }
        tr[d][mid + 1] = new_node(a[mid + 1]);
        for (int i = mid + 2; i <= r; ++i) {
            tr[d][i] = merge(tr[d][i - 1], new_node(a[i]));
        }
        build(u << 1, l, mid, d + 1);
        build(u << 1 | 1, mid + 1, r, d + 1);
    }
}

ll query(int l, int r) {
    if (l == r) return a[l];
    int d = logn[p[l]] - logn[p[l] ^ p[r]];
    return merge(tr[d][l], tr[d][r]).subsum;
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    int l = 1 << (int)ceil(log2(n));
    init(l);
    build(1, 1, l, 1);
    for (int i = 1; i <= m; ++i) {
        int l = read(), r = read();
        write(query(l, r), '\n');
    }
    flush();
    return 0;
}