洛谷 P4694
一个比较显然的网络流建模。如图所示用 \((流量，费用)\)表示一条边，增广 \(k\) 次的费用就是答案。
然后就是模拟费用流的部分。这种只有一条链的图（去掉 \(s, t\)）是比较经典的。因为它只有两种流法。（如下图）
正着流没有什么限制，只需要与 \(s, t\) 相连的边有流量即可。相当于选 \(i \le j\)，\(a_i, b_j\) 都没被选，然后选它们。直接用线段树维护区间 \(mina, minb\) 和答案即可。
反着流就麻烦一些，相当于选 \(i \ge j\)，然后选 \(a_i, b_j\)，但是要求 \(i \rightarrow j\) 都有流量（即 \(j \rightarrow i\) 的正向边都流过了）。看起来也可以用线段树维护 \(> 0\) 的连续段做，就是类似最大子段和一样的维护区间右端的极长 \(b\) 最小值 ，和区间左端极长 \(a\) 最小值 。
但是一增广就炸了，增广其实就是将某个区间的流量都 \(+1/-1\)，但是线段树就无法维护 \(> 0\) 的段了。这有一个小 trick，就是线段树维护 \(>\) 当前区间最小值 的连续段，合并时如果一边的最小值大于另一边，那么这一段都是可流的，所以同时像正流一样维护没有限制时的答案即可。
记得在维护值的同时还要维护下标。
时间复杂度：\(O(n \log n)\)
这种图时一条链的，还有很多变种，如流量是有限的，链上边有费用等，都可以用线段树模拟。