maxq

#include <cstdio>
#include <algorithm>
using namespace std;

#define FIN "maxq.in"
#define FOUT "maxq.out"

#define MAX_N (1<<18)
#define max(a, b) ((a) > (b) ? (a) : (b))

int N, M;
int v[MAX_N];
long long A[MAX_N<<1], B[MAX_N<<1], C[MAX_N<<1], Sum[MAX_N<<1];

#define lf (n<<1)
#define rt (lf+1)
#define md ((l+r)>>1)

void build(int n, int l, int r) {
    if (l == r) {
        A[n] = B[n] = C[n] = max(v[l], 0);
        Sum[n] = v[l];
    } else {
        build(lf, l, md);
        build(rt, md+1, r);
        A[n] = max(A[lf], Sum[lf]+A[rt]);
        B[n] = max(B[lf]+Sum[rt], B[rt]);
        C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);
        Sum[n] = Sum[lf]+Sum[rt];
    }
}

int p, x;

void update(int n, int l, int r) // p, x
{
    if (l == r) {
        A[n] = B[n] = C[n] = max(x, 0);
        Sum[n] = x;
    } else {
        if (p <= md) update(lf,    l, md);
        else         update(rt, md+1,  r);

        A[n] = max(A[lf], Sum[lf]+A[rt]);
        B[n] = max(B[lf]+Sum[rt], B[rt]);
        C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);

        Sum[n] = Sum[lf]+Sum[rt];
    }
}

int a, b;
long long ans, S;

void query(int n, int l, int r) // a, b
{
    if (a <= l && r <= b) {
        if (S < 0) S = 0;
        ans = max(ans, max(S+A[n], C[n]));
        S = max(S+Sum[n], B[n]);
    } else {
        if (a <= md) query(lf,    l, md);
        if (b >  md) query(rt, md+1,  r);
    }
}

int main()
{
    int i, t, v1, v2;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf("%d", v+i);
    build(1, 1, N);
    scanf("%d", &M);
    while (M--) {
        scanf("%d %d %d", &t, &v1, &v2);
        if (t == 0) { // update
            p = v1+1;
            x = v2;
            update(1, 1, N);
        } else { // query
            S = ans = 0;
            a = v1+1;
            b = v2+1;
            query(1, 1, N);

            printf("%lld\n", ans);
        }
    }
    return 0;
}