样例可以顺利通过

#include <bits/stdc++.h>
#define int long long
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
using namespace std;

const int N = 800005;

int n, m, a[N];

struct Node {
	int ms, ls, rs;
	int mlp, mrp, lp, rp;
}; 

struct Tree {
	Node maxt, mint;
	int sum;
};

Tree tree[N];
int lazy[N];
int l1[N], r1[N];

inline Tree pushup(Tree l, Tree r) {
	Tree res;
	res.sum = l.sum + r.sum;
	
	// update ms 
	if (l.maxt.ms > r.maxt.ms) {
		res.maxt.ms = l.maxt.ms;
		res.maxt.mlp = l.maxt.mlp;
		res.maxt.mrp = l.maxt.mrp;
	} else {
		res.maxt.ms = r.maxt.ms;
		res.maxt.mlp = r.maxt.mlp;
		res.maxt.mrp = r.maxt.mrp;
	}
	if (l.maxt.rs + r.maxt.ls > res.maxt.ms) {
		res.maxt.ms = l.maxt.rs + r.maxt.ls;
		res.maxt.mlp = l.maxt.rp;
		res.maxt.mrp = r.maxt.lp;
	}
	
	// update ls
	if (l.maxt.ls > l.sum + r.maxt.ls) {
		res.maxt.ls = l.maxt.ls;
		res.maxt.lp = l.maxt.lp;
	} else {
		res.maxt.ls = l.sum + r.maxt.ls;
		res.maxt.lp = r.maxt.lp;
	}
	
	// update rs
	if (r.maxt.rs > r.sum + l.maxt.rs) {
		res.maxt.rs = r.maxt.rs;
		res.maxt.rp = r.maxt.rp;
	} else {
		res.maxt.rs = r.sum + l.maxt.rs;
		res.maxt.rp = l.maxt.rp;
	}
	
	// update ms 
	if (l.mint.ms < r.mint.ms) {
		res.mint.ms = l.mint.ms;
		res.mint.mlp = l.mint.mlp;
		res.mint.mrp = l.mint.mrp;
	} else {
		res.mint.ms = r.mint.ms;
		res.mint.mlp = r.mint.mlp;
		res.mint.mrp = r.mint.mrp;
	}
	if (l.mint.rs + r.mint.ls < res.mint.ms) {
		res.mint.ms = l.mint.rs + r.mint.ls;
		res.mint.mlp = l.mint.rp;
		res.mint.mrp = r.mint.lp;
	}
	
	// update ls
	if (l.mint.ls < l.sum + r.mint.ls) {
		res.mint.ls = l.mint.ls;
		res.mint.lp = l.mint.lp;
	} else {
		res.mint.ls = l.sum + r.mint.ls;
		res.mint.lp = r.mint.lp;
	}
	
	// update rs
	if (r.mint.rs < r.sum + l.mint.rs) {
		res.mint.rs = r.mint.rs;
		res.mint.rp = r.mint.rp;
	} else {
		res.mint.rs = r.sum + l.mint.rs;
		res.mint.rp = l.mint.rp;
	}
	
	return res;
}

inline void pushdown(int x) {
	if (!lazy[x]) return;
	
	int l = lc(x), r = rc(x);
	
	// update lchild
	swap(tree[l].maxt, tree[l].mint);
	tree[l].maxt.ms *= -1;
	tree[l].maxt.ls *= -1;
	tree[l].maxt.rs *= -1;
	tree[l].mint.ms *= -1;
	tree[l].mint.ls *= -1;
	tree[l].mint.rs *= -1;
	
	// update rchild
	swap(tree[r].maxt, tree[r].mint);
	tree[r].maxt.ms *= -1;
	tree[r].maxt.ls *= -1;
	tree[r].maxt.rs *= -1;
	tree[r].mint.ms *= -1;
	tree[r].mint.ls *= -1;
	tree[r].mint.rs *= -1;
	
	lazy[l] ^= 1;
	lazy[r] ^= 1;
	lazy[x] = 0; 
}

inline void build(int x, int l, int r) {
	if (l == r) {
		tree[x].maxt.mlp = tree[x].maxt.mrp = tree[x].maxt.lp = tree[x].maxt.rp = l;
		tree[x].maxt.ms = tree[x].maxt.ls = tree[x].maxt.rs = a[l];
		
		tree[x].mint.mlp = tree[x].mint.mrp = tree[x].mint.lp = tree[x].mint.rp = l;
		tree[x].mint.ms = tree[x].mint.ls = tree[x].mint.rs = a[l];
		
		tree[x].sum = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(lc(x), l, mid);
	build(rc(x), mid + 1, r);
	tree[x] = pushup(tree[lc(x)], tree[rc(x)]);
}

inline void update(int x, int l, int r, int pos, int val) {
	if (l == r) {
		a[l] = val;
		
		tree[x].maxt.mlp = tree[x].maxt.mrp = tree[x].maxt.lp = tree[x].maxt.rp = l;
		tree[x].maxt.ms = tree[x].maxt.ls = tree[x].maxt.rs = a[l];
		
		tree[x].mint.mlp = tree[x].mint.mrp = tree[x].mint.lp = tree[x].mint.rp = l;
		tree[x].mint.ms = tree[x].mint.ls = tree[x].mint.rs = a[l];
		
		tree[x].sum = a[l];
		return;
	}
	int mid = l + r >> 1;
	pushdown(x); 
	if (pos <= mid) update(lc(x), l, mid, pos, val);
	else update(rc(x), mid + 1, r, pos, val);
	tree[x] = pushup(tree[lc(x)], tree[rc(x)]);
}

inline void reverse(int x, int l, int r, int pl, int pr) {
	if (pl <= l && r <= pr) {
		swap(tree[x].maxt, tree[x].mint);
		tree[x].maxt.ms *= -1;
		tree[x].maxt.ls *= -1;
		tree[x].maxt.rs *= -1;
		tree[x].mint.ms *= -1;
		tree[x].mint.ls *= -1;
		tree[x].mint.rs *= -1;
		lazy[x] ^= 1;
		return;
	}
	int mid = l + r >> 1;
	pushdown(x);
	if (pl <= mid) reverse(lc(x), l, mid, pl, pr);
	if (mid < pr) reverse(rc(x), mid + 1, r, pl, pr);
	tree[x] = pushup(tree[lc(x)], tree[rc(x)]);
}

inline Tree query(int x, int l, int r, int pl, int pr) {
	if (pl <= l && r <= pr) return tree[x];
	int mid = l + r >> 1;
	pushdown(x);
	if (pl <= mid && mid < pr) {
		Tree lt, rt;
		lt = query(lc(x), l, mid, pl, pr);
		rt = query(rc(x), mid + 1, r, pl, pr);
		return pushup(lt, rt);
	} 
	if (pl <= mid) return query(lc(x), l, mid, pl, pr);
	if (mid < pr) return query(rc(x), mid + 1, r, pl, pr);
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	build(1, 1, n);
	scanf("%lld", &m);
	int op, l, r, k, k1; 
	int ans, ret;
	Tree t;
	while (m--) {
		scanf("%lld %lld %lld", &op, &l, &r);
		if (op == 0) {
			update(1, 1, n, l, r);
		} else {
			scanf("%lld", &k);
			k1 = k;
			ans = ret = 0;
			while (k) {
				t = query(1, 1, n, l, r);
				ret += t.maxt.ms;
				ans = max(ans, ret);
				reverse(1, 1, n, t.maxt.mlp, t.maxt.mrp);
				l1[k] = t.maxt.mlp;
				r1[k] = t.maxt.mrp;
				k--;
			}
			for (int i = 1; i <= k1; i++) {
				reverse(1, 1, n, l1[i], r1[i]);
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}