Luogu 6821 PA2012 Tanie linie

这里只讲加强版，这是严格弱化。

结论是贪心。每次取出最大和连续子段，目前答案加上这个子段和，然后再把这个子段取反（相反数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;
}