悬关求调

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
#define inf (ll)(2e9)
using namespace std;

typedef long long ll;
ll n, m, a[500005], k, u, v, w;

struct Tree {
    ll l, lnum, r, rnum, sum, ans, num, len, tag;
    Tree operator+(const Tree & tr) const {
        Tree t0;
        if (sum + tr.l > l) {
            t0.lnum = len + tr.lnum;
            t0.l = sum + tr.l;
        } else {
            t0.lnum = lnum;
            t0.l = l;
        }
        if (r + tr.sum > tr.r) {
            t0.rnum = rnum + tr.len;
            t0.r = r + tr.sum;
        } else {
            t0.rnum = tr.rnum;
            t0.r = tr.r;
        }
        t0.sum = sum + tr.sum;
        if (max({ans, tr.ans, r + tr.l}) == ans) {
            t0.num = num;
            t0.ans = ans;
        } else if (max({ans, tr.ans, r + tr.l}) == tr.ans) {
            t0.num = tr.num;
            t0.ans = tr.ans;
        } else {
            t0.num = rnum + tr.lnum;
            t0.ans = r + tr.l;
        }
        t0.len = len + tr.len;
        return t0;
    }
} t[2000005];

inline void move(ll x, ll tag) {
    t[x].tag += tag;
    t[x].l += tag * t[x].lnum;
    t[x].r += tag * t[x].rnum;
    t[x].ans += tag * t[x].num;
    t[x].sum += tag * t[x].len;
}

inline void up(ll x) {
    t[x] = t[ls] + t[rs];
}

inline void down(ll x, ll l, ll r) {
    move(ls, t[x].tag);
    move(rs, t[x].tag);
    t[x].tag = 0;
}

void build(ll x, ll l, ll r) {
    if (l == r) {
        t[x] = {a[l], 1, a[l], 1, a[l], a[l], 1, 1, 0};
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    up(x);
}

Tree query(ll x, ll l, ll r, ll ql, ll qr) {
    if (ql <= l && r <= qr) return t[x];
    Tree ans({-inf, 0, -inf, 0, 0, -inf, 0, 0, 0});
    down(x, l, r);
    if (ql <= mid) {
        ans = ans + query(ls, l, mid, ql, qr);
    }
    if (mid < qr) {
        ans = ans + query(rs, mid + 1, r, ql, qr);
    }
    return ans;
}

void update(ll x, ll l, ll r, ll ql, ll qr, ll tag) {
    if (ql <= l && r <= qr) {
        move(x, tag);
        return ;
    }
    down(x, l, r);
    if (ql <= mid) {
        update(ls, l, mid, ql, qr, tag);
    }
    if (mid < qr) {
        update(rs, mid + 1, r, ql, qr, tag);
    }
    up(x);
}

int main() {
    scanf("%lld%lld", &n, &m);
    for (ll i(1); i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    while (--m > -1) {
        scanf("%lld%lld%lld", &k, &u, &v);
        if (u > v) u ^= v ^= u ^= v;
        if (k & 1) {
            scanf("%lld", &w);
            update(1, 1, n, u, v, w);
        } else {
            printf("%lld\n", max(query(1, 1, n, u, v).ans, 0ll));
        }
    }
    return 0;
}