这里只讲加强版，这是严格弱化。
结论是贪心。每次取出最大和连续子段，目前答案加上这个子段和，然后再把这个子段取反（相反数T），然后求整个过程答案的最大值。
考虑费用流模型。对于 \(i\le n\)，\(S\to i\) 连边，\(i\to T\) 连边，流量为 \(1\) 费用为 \(0\)；\(i\to i+1\) 连边，流量为 \(1\) 费用为 \(-a_i\)。求费用流的时候，取 \(S\to i\to j\to T\) 流，代表取了 \([i,j)\) 这个区间。不难发现上面贪心策略对应的就是费用流的贪心，所以这也叫模拟费用流。
所以只用维护 \(2\) 种操作：
- 求出区间最大子段和以及其两个端点 \(l,r\)。
- 支持区间取相反数。
考虑用线段树维护这个东西。
正常的区间最大子段和需要维护 \(lmx,rmx,mx\) 三个值嘛，分别表示取左端点的最大子段，取右端点的最大子段和整个区间的最大子段。由于要求端点位置，还需要维护 \(lx,rx,llx,rrx\) 表示取右端点的最大子段的左端点、取左端点最大子段的右端点、以及这个区间最大子段的左右端点。合并的时候简单讨论一下就可以了。
现在要区间取反，所以添加一个标记，把最大改成最小，再维护 \(lmn,rmn,mn,ln,rn,lln,rrn\) 七个值即可，也是简单讨论一下。
然后询问之间互相独立，要开个栈存下所有取反操作，逐一还原回去。
复杂度 \(O(qk\log n)\)，这是加强版的代码。
#include <bits/stdc++.h>
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define rd read
#define wr write
#define pc putchar
#define pi pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ins insert
#define era erase
inline int read () {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(int x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using vbzIO::read;
using vbzIO::write;
const int N = 1e5 + 100;
bool chkmx(int &x, int y) { return x < y ? (x = y, 1) : 0; }
bool chkmn(int &x, int y) { return x > y ? (x = y, 1) : 0; }
struct seg {
int sum;
int lmx, rmx, mx, lx, rx, llx, rrx;
int lmn, rmn, mn, ln, rn, lln, rrn;
seg operator + (const seg &rhs) const {
seg ans;
ans.sum = sum + rhs.sum;
ans.lmx = lmx, ans.llx = llx, ans.rmx = rhs.rmx, ans.rrx = rhs.rrx;
if (chkmx(ans.lmx, sum + rhs.lmx)) ans.llx = rhs.llx;
if (chkmx(ans.rmx, rhs.sum + rmx)) ans.rrx = rrx;
ans.mx = mx, ans.lx = lx, ans.rx = rx;
if (chkmx(ans.mx, rhs.mx)) ans.lx = rhs.lx, ans.rx = rhs.rx;
if (chkmx(ans.mx, rmx + rhs.lmx)) ans.lx = rrx, ans.rx = rhs.llx;
ans.lmn = lmn, ans.lln = lln, ans.rmn = rhs.rmn, ans.rrn = rhs.rrn;
if (chkmn(ans.lmn, sum + rhs.lmn)) ans.lln = rhs.lln;
if (chkmn(ans.rmn, rhs.sum + rmn)) ans.rrn = rrn;
ans.mn = mn, ans.ln = ln, ans.rn = rn;
if (chkmn(ans.mn, rhs.mn)) ans.ln = rhs.ln, ans.rn = rhs.rn;
if (chkmn(ans.mn, rmn + rhs.lmn)) ans.ln = rrn, ans.rn = rhs.lln;
return ans;
}
} tr[N << 2];
int n, m, a[N], tag[N << 2];
stack<pi> opt;
void revt(seg &x) {
seg ans;
ans.sum = -x.sum;
ans.lmx = -x.lmn, ans.llx = x.lln, ans.rmx = -x.rmn, ans.rrx = x.rrn;
ans.lmn = -x.lmx, ans.lln = x.llx, ans.rmn = -x.rmx, ans.rrn = x.rrx;
ans.mx = -x.mn, ans.lx = x.ln, ans.rx = x.rn;
ans.mn = -x.mx, ans.ln = x.lx, ans.rn = x.rx;
x = ans;
}
void sett(int l, int x) {
tr[x] = (seg) {
a[l],
a[l], a[l], a[l], l, l, l, l,
a[l], a[l], a[l], l, l, l, l
};
}
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void pushup(int x) { tr[x] = tr[ls] + tr[rs]; }
void pushrev(int x) { tag[x] ^= 1, revt(tr[x]); }
void pushdown(int x) {
if (!tag[x]) return;
pushrev(ls), pushrev(rs);
tag[x] = 0;
}
void build(int l, int r, int x) {
if (l == r) return sett(l, x);
build(l, mid, ls), build(mid + 1, r, rs), pushup(x);
}
void upd(int l, int r, int p, int x) {
if (l == r) return sett(l, x);
pushdown(x);
if (p <= mid) upd(l, mid, p, ls);
else upd(mid + 1, r, p, rs);
pushup(x);
}
void rev(int l, int r, int s, int t, int x) {
if (s <= l && r <= t) return pushrev(x);
pushdown(x);
if (s <= mid) rev(l, mid, s, t, ls);
if (t > mid) rev(mid + 1, r, s, t, rs);
pushup(x);
}
seg qry(int l, int r, int s, int t, int x) {
if (s <= l && r <= t) return tr[x];
pushdown(x);
if (s > mid) return qry(mid + 1, r, s, t, rs);
else if (t <= mid) return qry(l, mid, s, t, ls);
else return qry(l, mid, s, t, ls) + qry(mid + 1, r, s, t, rs);
}
int main() {
n = rd();
for (int i = 1; i <= n; i++) a[i] = rd();
build(1, n, 1), m = rd();
while (m--) {
int op = rd(), l = rd(), r = rd();
if (!op) a[l] = r, upd(1, n, l, 1);
else {
int k = rd(), ans = 0, sum = 0;
while (k--) {
seg tp = qry(1, n, l, r, 1);
chkmx(ans, sum += tp.mx);
opt.push(mp(tp.lx, tp.rx));
rev(1, n, tp.lx, tp.rx, 1);
}
while (!opt.empty())
rev(1, n, opt.top().fi, opt.top().se, 1), opt.pop();
wr(ans), puts("");
}
}
return 0;
}