懒得卡空间了！

我们考虑对于一段区间来说，在全局加 $x$ 后，长度为 $l$ 的段的最优答案是啥。不难发现是 $lx + b$ ，其中 $b$ 为长度为 $l$ 段的和的最大值。因此我们可以对每个 $l = 1\sim n$ ，求出一条直线，然后对这个直线求一个凸包就可以做询问在全局加 $x$ 的情况下的和了。

然后考虑区间询问怎么办。首先我们可以把区间询问拆成 $O(\log n)$ 个线段树节点。然后对每个节点，我们维护出最大的后缀和，最大的前缀和，最大的区间本身子段，以及区间的和。之需要对这 $O(\log n)$ 个节点做 $dp[u] = pre_u + S_{u-1} + \max_{v < u}(suf_v - S_v)$ 这个东西即可，这个玩意是 $O(\log n)$ 的。所以我们之需要对一个线段树区间维护这几个东西即可。

不难发现最大后缀和和最大前缀和都可以维护一个关于 $x$ 的凸包。然后在 pushup 求出最大子段和的时候，我们要做的其实就是把 左右儿子的后缀凸包和前缀凸包加起来 再和 左右儿子的最大子段和凸包 chkmax 后的结果 再 chkmax 一次即可。看起来凸包的大小会膨胀，但是事实上由于本质不同斜率只有 $O(len)$ 个，所以实际上每个位置的凸包大小也是 $O(len)$ 的。而这几个过程都可以归并来做，因此复杂度是 $O(n\log n)$ 的。

考虑询问的过程，看起来我们需要在每个凸包上二分一下 $x$ ，事实上离线询问后，我们可以按照 $x$ 排序处理询问。这样就之需要移动一个指针即可，复杂度 $O(n\log n + m\log n)$ 。看起来足以通过本题。但是事实上这玩意有一个 $O(n\log n)$ 的空间，即使压紧开在构造数据也需要 300MB 左右，炸掉了 128MB ，因此需要一些优秀的卡空间技巧来通过此题。具体来说，需要在对每层建立凸包后丢弃掉下面一层，然后把询问挂在节点上之类的操作。最后可以卡到严格 $O(n)$ 空间。

最后放一个随机数据能过，但是构造数据会被卡到两到三倍左右空间的代码：

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
#pragma pack(1)
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define mem(a) memset(a, 0, sizeof a)
typedef long long ll;
int n, m;
int A[MAXN];

struct line {
    int k;
    ll b;
    line(int a = 0, ll b = 0) : k(a), b(b) {}
    bool operator<(line x) { return k == x.k ? b < x.b : k < x.k; }
    line operator+(line x) { return line(k + x.k, b + x.b); }
    ll gval(ll x) { return k * 1ll * x + b; }
};
line bs[6000006], *cur;
int tot = 0;
struct MLE {
    line* st;
    int size;
    void ini() { st = cur, size = 0; }
    void fx() { cur = st + size; }
    line& operator[](int a) { return *(st + a); }
    void pop_back() { --size; }
    void push_back(line r) {
        *(st + size) = r;
        ++size;
    }
} pmx[MAXN << 2], smx[MAXN << 2], mx[MAXN << 2];
ll S[MAXN << 2];

inline double cp(line a, line b) {
    if (a.k == b.k)
        return -1e18;
    return (b.b - a.b * 1.) / (a.k - b.k);
}

inline void ins(MLE& s, line t) {
    while (s.size > 1 && cp(s[s.size - 1], s[s.size - 2]) > cp(s[s.size - 1], t)) s.pop_back();
    if (s.size == 1 && s[0].k == t.k)
        s.pop_back();
    s.pb(t);
}

MLE add(MLE& A, MLE& B) {
    if (!A.size)
        return B;
    if (!B.size)
        return A;
    int p = 0, q = 0;
    MLE re;
    re.ini();
    while (p + 1 < A.size || q + 1 < B.size) {
        if (p + 1 == A.size) {
            ins(re, A[p] + B[q]), ++q;
            continue;
        }
        if (q + 1 == B.size) {
            ins(re, A[p] + B[q]), ++p;
            continue;
        }
        ins(re, A[p] + B[q]);
        if (cp(A[p], A[p + 1]) < cp(B[q], B[q + 1]))
            ++p;
        else
            ++q;
    }
    ins(re, A[p] + B[q]);
    re.fx();
    return re;
}

void build(int rt, int l, int r) {
    if (l == r) {
        mx[rt].ini(), mx[rt].pb(line(1, A[l])), mx[rt].fx();
        smx[rt].ini(), smx[rt].pb(line(1, A[l])), smx[rt].fx();
        pmx[rt].ini(), pmx[rt].pb(line(1, A[l])), pmx[rt].fx();
        S[rt] = A[l];
        return;
    }
    int m = l + r >> 1;
    build(rt << 1, l, m), build(rt << 1 | 1, m + 1, r);
    int j = 0;
    MLE f;
    f.ini();
    rep(i, 0, mx[rt << 1].size - 1) {
        while (j < mx[rt << 1 | 1].size && mx[rt << 1 | 1][j] < mx[rt << 1][i]) {
            ins(f, mx[rt << 1 | 1][j]);
            ++j;
        }
        ins(f, mx[rt << 1][i]);
    }
    while (j < mx[rt << 1 | 1].size) ins(f, mx[rt << 1 | 1][j]), ++j;
    f.fx();
    MLE con = add(smx[rt << 1], pmx[rt << 1 | 1]);
    j = 0;
    mx[rt].ini();
    rep(i, 0, f.size - 1) {
        while (j < con.size && con[j] < f[i]) {
            ins(mx[rt], con[j]), ++j;
        }
        ins(mx[rt], f[i]);
    }
    while (j < con.size) ins(mx[rt], con[j]), ++j;
    mx[rt].fx();
    pmx[rt].ini();
    ll s = 0;
    rep(i, l, r) s += A[i], ins(pmx[rt], line(i - l + 1, s));
    pmx[rt].fx();
    s = 0;
    smx[rt].ini();
    per(i, r, l) s += A[i], ins(smx[rt], line(r - i + 1, s));
    smx[rt].fx();
    S[rt] = S[rt << 1] + S[rt << 1 | 1];
}

struct que {
    ll x;
    int l, r, idx;
} Q[600006];

vector<ll> sl, sr, su;
ll sm;
ll px;

void doit(MLE& s) {
    while (s.size > 1 && px > cp(s[0], s[1])) ++s.st, --s.size;
}

void gt(int rt, int len) {
    if (len == 1) {
        ll v = mx[rt][0].gval(px);
        sm = max(sm, v);
        sl.pb(v), sr.pb(v), su.pb(v);
        return;
    }
    doit(mx[rt]), sm = max(sm, mx[rt][0].gval(px));
    doit(smx[rt]), sl.pb(smx[rt][0].gval(px));
    doit(pmx[rt]), sr.pb(pmx[rt][0].gval(px));
    su.pb(S[rt] + len * 1ll * px);
}

void fuck(int rt, int l, int r, int L, int R) {
    if (L <= l && R >= r) {
        gt(rt, r - l + 1);
        return;
    }
    int m = l + r >> 1;
    if (L <= m)
        fuck(rt << 1, l, m, L, R);
    if (R > m)
        fuck(rt << 1 | 1, m + 1, r, L, R);
}

ll as[600006];

void solve() {
    //	cout << sizeof( bs ) << ' ' << sizeof( line* ) << endl;
    //	cout << sizeof( line ) << endl;
    cur = bs;
    cin >> n >> m;
    rep(i, 1, n) scanf("%d", A + i);
    build(1, 1, n);
    ll cx = 0;
    int cn = 0;
    rep(i, 1, m) {
        int op, x, y;
        scanf("%d", &op);
        if (op == 1)
            scanf("%d", &x), cx += x;
        else
            scanf("%d%d", &x, &y), ++cn, Q[cn] = (que){ cx, x, y, cn };
    }
    sort(Q + 1, Q + 1 + cn, [&](que a, que b) { return a.x < b.x; });
    rep(i, 1, cn) {
        ll tx = Q[i].x;
        int l = Q[i].l, r = Q[i].r;
        sm = 0;
        px = tx;
        su.clear(), sl.clear(), sr.clear();
        fuck(1, 1, n, l, r);
        int sz = su.size() - 1;
        rep(j, 1, sz) su[j] += su[j - 1];
        ll tmx = -1e18;
        rep(j, 0, sz) {
            if (j)
                sm = max(sm, sr[j] + su[j - 1] + tmx);
            tmx = max(tmx, sl[j] - su[j]);
        }
        as[Q[i].idx] = sm;
    }
    rep(i, 1, cn) printf("%lld\n", as[i]);
    //	cerr << cur - bs << endl;
}

signed main() {
    //	freopen("y0.in","r",stdin);
    //	freopen("out","w",stdout);
    //    int T;cin >> T;while( T-- ) solve();
    solve();
}