求调（

感觉可能是野指针，明天改写个数组版

#include <algorithm>
using std::max;

using i32 = long long;
using i64 = long long;

#define N 500004

const i32 INF = 0x3f3f3f3f;

struct Node {
    Node *lc, *rc;
    i32 l, r;
    i32 mx, lmx, rmx, sum;
    i32 mid;

    void init(i32 L, i32 R) {
        l = L, r = R;
        mid = (l + r) >> 1;
        sum = 0;
        mx = lmx = rmx = -INF;
    }
    void push_up() {
        lmx = lc->lmx;
        if (lc->lmx == lc->sum) lmx = max(lmx, lc->lmx + rc->lmx);
        rmx = rc->rmx;
        if (rc->rmx == rc->sum) rmx = max(rmx, rc->rmx + lc->rmx);
        sum = lc->sum + rc->sum;
        mx = max(max(lmx, rmx), lc->rmx + rc->lmx);
    }

    Node operator+(Node b) {
        Node res;
        res.lc = this, res.rc = &b;
        res.push_up();
        return res;
    }
} stree[N << 2], *null, *root;
Node* tot = stree;

i32 a[N], n;

void build(Node* nod, i32 l, i32 r) {
    nod->init(l, r);
    if (l == r) {
        nod->mx = nod->lmx = nod->rmx = nod->sum = a[l];
        nod->lc = nod->rc = null;
    } else {
        nod->lc = ++tot;
        build(nod->lc, l, nod->mid);
        nod->rc = ++tot;
        build(nod->rc, nod->mid + 1, r);
        nod->push_up();
    }
}

Node query(Node* nod, i32 l, i32 r) {
    if (nod->l == nod->r)
        return *nod;
    else {
        if (nod->mid < l)
            return query(nod->rc, l, r);
        else if (nod->mid >= r)
            return query(nod->lc, l, r);
        else
            return query(nod->lc, l, nod->mid) + query(nod->rc, nod->mid, r);
    }
}

i32 t1, t2;

int main() {
    null = tot;
    root = ++tot;
    null->init(0, 0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build(root, 1, n);
    cin >> n;
    ++n;
    while (--n) {
        cin >> t1 >> t2;
        cout << query(root, t1, t2).mx << endl;
    }

    return 0;
}