我的代码复杂度是 $O(m\log n \times k^2)$。

#include <bits/stdc++.h>
#define db double
#define ll int
#define ex exit(0)
#define endl "\n"
#define inl inline
#define null NULL
#define pll pair<ll,ll>
#define mkp(a,b) make_pair(a,b)
#define INF -2122219135
using namespace std;
ll cnt = 0;
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}
inline void out(int n) {
	if (n < 0) {
		putchar('-');
		n = -n;
	}
	if (n >= 10) {
		out(n / 10);
	}
	putchar(n % 10 + '0');
}
ll n;
ll a[100005];
inl ll lc(ll p) {
	return p << 1;
}
inl ll rc(ll p) {
	return p << 1 | 1;
}
struct node {
	ll f[4][25];
} t[400005];
inl ll getans(ll x, ll y) {
	if (x != INF && y != INF) {
		return x + y;
	} else if (x != INF) {
		return x;
	} else if (y != INF) {
		return y;
	} else {
		return INF;
	}
}
inl void pushup(node &tmp, node l, node r) {
	memset(tmp.f, -0x7f, sizeof(tmp.f));
	for (int i = 0; i <= 20; i++) {
		for (int j = 0; j <= 21 - i; j++) {
			cnt++;
			if (!i && !j) {
				continue;
			}
			tmp.f[0][i + j] = max(tmp.f[0][i + j], getans(l.f[0][i], r.f[0][j])),
			                  tmp.f[0][i + j] = max(tmp.f[0][i + j], getans(l.f[0][i], r.f[1][j])),
			                                    tmp.f[0][i + j] = max(tmp.f[0][i + j], getans(l.f[2][i], r.f[0][j]));
			if (i + j == 1) {
			} else {
				if (i == 0 || j == 0) {
					tmp.f[0][i + j] = max(tmp.f[0][i + j], getans(l.f[2][i], r.f[1][j]));
				} else {
					tmp.f[0][i + j - 1] = max(tmp.f[0][i + j - 1], getans(l.f[2][i], r.f[1][j]));
				}
			}
			if (i != 0) {
				tmp.f[1][i + j] = max(tmp.f[1][i + j], getans(l.f[1][i], r.f[0][j])),
				                  tmp.f[1][i + j] = max(tmp.f[1][i + j], getans(l.f[1][i], r.f[1][j])),
				                                    tmp.f[1][i + j] = max(tmp.f[1][i + j], getans(l.f[3][i], r.f[0][j]));
				if (i + j == 1) {
				} else {
					if (j == 0) {
						tmp.f[1][i] = max(tmp.f[1][i], getans(l.f[3][i], r.f[1][j]));
					} else {
						tmp.f[1][i + j - 1] = max(tmp.f[1][i + j - 1], getans(l.f[3][i], r.f[1][j]));
					}
				}
			}
			if (j != 0) {
				tmp.f[2][i + j] = max(tmp.f[2][i + j], getans(l.f[0][i], r.f[2][j])),
				                  tmp.f[2][i + j] = max(tmp.f[2][i + j], getans(l.f[2][i], r.f[2][j])),
				                                    tmp.f[2][i + j] = max(tmp.f[2][i + j], getans(l.f[0][i], r.f[3][j]));
				if (i + j == 1) {
				} else {
					if (i == 0) {
						tmp.f[2][j] = max(tmp.f[2][j], getans(l.f[2][i], r.f[3][j]));
					} else {
						tmp.f[2][i + j - 1] = max(tmp.f[2][i + j - 1], getans(l.f[2][i], r.f[3][j]));
					}
				}
			}
			if (i == 0 || j == 0) {
				continue;
			}
			tmp.f[3][i + j] = max(tmp.f[3][i + j], getans(l.f[1][i], r.f[2][j])),
			                  tmp.f[3][i + j] = max(tmp.f[3][i + j], getans(l.f[3][i], r.f[2][j])),
			                                    tmp.f[3][i + j] = max(tmp.f[3][i + j], getans(l.f[1][i], r.f[3][j]));
			if (i + j == 1) {
			} else {
				tmp.f[3][i + j - 1] = max(tmp.f[3][i + j - 1], getans(l.f[3][i], r.f[3][j]));
			}
		}
	}
}
void build(ll p, ll l, ll r) {
	if (l == r) {
		memset(t[p].f, -0x7f, sizeof(t[p].f));
		t[p].f[3][1] = a[l];
		return ;
	}
	ll mid = (l + r) >> 1;
	build(lc(p), l, mid);
	build(rc(p), mid + 1, r);
	pushup(t[p], t[lc(p)], t[rc(p)]);
}
void upd(ll p, ll l, ll r, ll x, ll d) {
	if (l == r && r == x) {
		t[p].f[3][1] = d;
		return ;
	}
	ll mid = (l + r) >> 1;
	if (x <= mid) {
		upd(lc(p), l, mid, x, d);
	}
	if (mid < x) {
		upd(rc(p), mid + 1, r, x, d);
	}
	pushup(t[p], t[lc(p)], t[rc(p)]);
}
node query(ll p, ll l, ll r, ll ql, ll qr) {
	if (ql <= l && r <= qr) {
		return t[p];
	}
	ll mid = (l + r) >> 1;
	if (ql <= mid && mid < qr) {
		node tmp;
		pushup(tmp, query(lc(p), l, mid, ql, qr), query(rc(p), mid + 1, r, ql, qr));
		return tmp;
	} else if (ql <= mid) {
		return query(lc(p), l, mid, ql, qr);
	} else {
		return query(rc(p), mid + 1, r, ql, qr);
	}
}
int main() {
//	freopen("test.in", "r", stdin);
//	freopen("ababab.out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
	}
	build(1, 1, n);
	ll q;
	q = read();
	while (q--) {
		ll op;
		op = read();
		if (op == 0) {
			ll x = read(), val = read();
			upd(1, 1, n, x, val);
		}
		if (op == 1) {
			ll l = read(), r = read(), k = read();
			node ans = query(1, 1, n, l, r);
			ll answer = 0;
			for (int i = 1; i <= k; i++) {
				answer = max(answer, max(ans.f[0][i], max(ans.f[1][i], max(ans.f[2][i], ans.f[3][i]))));
			}
			out(answer);
			printf("\n");
		}
	}
	return 0;
}