rt，感觉是严格的 $O(nk+qklogn)$ 的，但是在 $n=q=10^4$ 的数据下就跑了 1s 多。

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define R register
#define vi vector<int>
#define vvi vector<vi>
#define INF (0x3f3f3f3f)
#define rep(i, l, r) for(R int i(l); i <= (r); ++ i) 
#define per(i, r, l) for(R int i(r); i >= (l); -- i) 
using namespace std;

namespace Fast_OI {
	char buf[1000000], *p1 = buf, *p2 = buf, obuf[1000000], *p3 = obuf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
	#define putchar(x) (p3-obuf<1000000?*p3++=x:(fwrite(obuf,1,p3-obuf,stdout),p3=obuf,*p3++=x))
	inline int read() {
		int x = 0; bool f = 1; char c = getchar();
		while (!isdigit(c)) { if (c == '-') f = 0; c = getchar(); }
		while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
		return f ? x : -x;
	}
	inline void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + 48);
	}
} using namespace Fast_OI;

const int N = 100005;

int n, Q;
int a[N];

const int M = 20;
vi operator + (vi& a, vi& b) {
	vi res(M + 1);  
	res[0] = a[0] + b[0];
	int p = 1, q = 1; 
	rep(i, 1, M) { 
		if (p > M) res[i] = res[i - 1] + b[q] - b[q - 1], ++ q;
		else if (q > M) res[i] = res[i - 1] + a[p] - a[p - 1], ++ p;
		else if (a[p] - a[p - 1] > b[q] - b[q - 1]) 
			 res[i] = res[i - 1] + a[p] - a[p - 1], ++ p;
		else res[i] = res[i - 1] + b[q] - b[q - 1], ++ q;
	} return res;
} 
void Cmax(vi& f, vi g) {
	rep(i, 0, M) f[i] = max(f[i], g[i]); 
}
void Smax(vi& f, vi g) {
	rep(i, 0, M - 1) f[i] = max(f[i], g[i + 1]);
}
vvi Merge(vvi f, vvi g) {
	vvi h(4);
	for (vi& x : h) x.resize(M + 1, -INF);
	Cmax(h[0], f[0] + g[0]); Smax(h[0], f[1] + g[2]);
	Cmax(h[1], f[0] + g[1]); Smax(h[1], f[1] + g[3]);
	Cmax(h[2], f[2] + g[0]); Smax(h[2], f[3] + g[2]);
	Cmax(h[3], f[2] + g[1]); Smax(h[3], f[3] + g[3]);
	return h;
}
struct Segment_tree {
	#define lc (u << 1)
	#define rc (u << 1 | 1)
	private : 
	vvi tr[N << 2];
	void push_up(int u) {
		tr[u] = Merge(tr[lc], tr[rc]);
	}
	void Set(vvi& x, int val) {
		x.clear(); x.resize(4);
		for (vi& v : x) v.resize(M + 1, val);
		x[0][0] = 0; x[1][0] = x[2][0] = x[3][0] = -INF;
	}
	public : 
	void Build(int u = 1, int l = 1, int r = n) {
		if (l == r) {
			Set(tr[u], a[l]);
			return;
		} int mid = (l + r) >> 1;
		Build(lc, l, mid); 
		Build(rc, mid + 1, r);
		push_up(u);
	}
	void Modify(int p, int x, int u = 1, int l = 1, int r = n) {
		if (l == r) {
			Set(tr[u], x);
			return;
		} int mid = (l + r) >> 1;
		if (p <= mid) Modify(p, x, lc, l, mid);
		else Modify(p, x, rc, mid + 1, r);
		push_up(u);
	}
	vvi Query(int bg, int nd, int u = 1, int l = 1, int r = n) {
 		if (bg <= l && r <= nd) return tr[u];
		int mid = (l + r) >> 1; vvi res; Set(res, 0);
		if (bg <= mid) res = Merge(res, Query(bg, nd, lc, l, mid));
		if (nd > mid) res = Merge(res, Query(bg, nd, rc, mid + 1, r));
		return res;
	}
	#undef lc
	#undef rc
}st;

int main()
{
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
	
	n = read();
	rep(i, 1, n) a[i] = read();
	st.Build(); Q = read();
	while (Q --) {
		int op, l, r, k;
		op = read();
		if (!op) {
			l = read(), k = read();
			st.Modify(l, k);
		} else {
			l = read(), r = read(), k = read();
			write(st.Query(l, r)[0][k]), putchar('\n');
		}
	} return fwrite(obuf,1,p3-obuf,stdout), 0; 
}