【题解】P4694 费用流 线段树 模拟费用流
ღꦿ࿐
·
·
题解
费用流建模显然。
因为决策都在一条链上，增广路的形态较少，考虑模拟费用流。
每一次增广一定选择了一对 $(a_i,b_j)$ 其中 $i\leq j$ 或 $i > j$ 且 $[i,j)$ 中这一段中均有大于 $0$ 的反向流量。
考虑分别维护两种信息。
第一种显然直接维护 $a,b$ 最值及其位置即可。
第二种较为复杂，展开叙述：
发现维护区间中 是否有 $0$ 这种相关的信息是不好维护的，因为涉及加法和值域，发现区间最小值是 $0$，经典地，把维护区间 $0$ 的信息考虑成维护区间最小值的信息：我们考虑维护区间内部不经过流量最小值的对，这样就能够在进行流量加法的时候方便地打 tag。
具体做法如下：
维护
区间内最小 $a,b$ 及它们的坐标 $ma,mb
区间内最小价值的 vab=a_i+b_i(i\leq j) 。
区间内最小价值的 vba1=b_i + a_j(i<j)。
区间内最小价值的 vba2=b_i + a_j(i<j\text{区间内 j 到 i 的流量均不为最小值})。
上方这个信息无法简单的合并，合并的时候考虑最小值来源于 左，右 或分别来源于左右。
首先无论如何子区间的最值是可以选择的。
如果最小值来源于左边，那么右边任意 a 都可以用用于更新答案，而左边可以更新答案的是一段后缀里面的 b，且这段后缀里面没有出现最值。
如果最小值来源于右边，那么左边任意 b 都可以用用于更新答案，而右边可以更新答案的是一段前缀里面的 b。
如果两边都有最小值，那么更新答案的一定是一段左边的后缀 b 和一段右边的前缀 a。
那么我们再考虑维护这个可行的前缀和后缀：
令 p 表示区间里的一段前缀满足 [l,p) 中的边流量都不达到区间最小值的前缀。
令 $s$ 表示区间里的一段前缀满足 $[s,r]$ 中的边流量都不达到区间最小值的前缀。
$suf$ 表示 $[s,r]$ 的最小值。
（区间开闭不同是因为上方可行条件是左闭右开的，此类细节需要注意）
这样就可以合并信息了。 仍然是根据最小值的来源，$pre$ 和 $suf$ 分别有可能是某个子区间的 $pre$ 和 $suf$ 或者就是某个子区间的 $a$，$b$ 的最小值。
push up 代码：
```cpp
struct node {
int Smn ;
ca ma,pre; cb mb,suf;
pr ab,ba,b_a;
//ma mb 最小值
// pre suf suf：不含S最小值的后缀里的最小a pre：不含最小值的前缀及其后方第一个的最小b
// ab ：一组ab，ba：不限制 的ba，b_a 限制 的 ba
} tr[N * 3];
#define ls x<<1
#define rs x<<1|1
#define mid ((l+r)>>1)
void up(int x) {
tr[x].Smn = min(tr[ls].Smn , tr[rs].Smn) ;
tr[x].ma = min(tr[ls].ma , tr[rs].ma) ;
tr[x].mb = min(tr[ls].mb , tr[rs].mb) ;
tr[x].ab = min({tr[ls].ab , tr[rs].ab , O(tr[ls].ma , tr[rs].mb)});
tr[x].ba = min({tr[ls].ba , tr[rs].ba , O(tr[rs].ma , tr[ls].mb)});
if(tr[x].Smn != tr[ls].Smn) {
// 最值仅来源于右儿子
// if(x == 7) cout << tr[ls].suf.v << "qwq\n";
tr[x].b_a = min({tr[ls].ba , tr[rs].b_a , O(tr[rs].pre , tr[ls].mb)});
tr[x].pre = min(tr[ls].ma , tr[rs].pre) ;
tr[x].suf = tr[rs].suf;
} else
if(tr[x].Smn != tr[rs].Smn) {
// 最值仅来源于左儿子
tr[x].b_a = min({tr[ls].b_a , tr[rs].ba , O(tr[rs].ma , tr[ls].suf)});
tr[x].suf = min(tr[ls].suf , tr[rs].mb) ;
tr[x].pre = tr[ls].pre ;
} else {
// 两边都有最值
tr[x].b_a = min({tr[ls].b_a , tr[rs].b_a , O(tr[rs].pre , tr[ls].suf)});
tr[x].pre = tr[ls].pre ;
tr[x].suf = tr[rs].suf ;
}
}
```
[full code](https://codeforces.com/contest/802/submission/212482777)