费用流相关处理：
最通用的模拟费用流做法——关键点法，找到若干关键点，维护两两关键点之间”不经过别的关键点“的最短路径。每次在新图上跑最短路，然后回到原图增广。时间复杂度 \(O(k^2n\log n+k^3n)\)
找 \(k\) 个不交区间：可以看作 \(k\) 个任意的区间做对称差。
反悔贪心：有意义的任意两方案可以轻易转化。//不太好理解
flow 相关例题好像不是很有一个能穿起来的逻辑，只有若干零星的建模。
//后续再补
图论建模，有一些模式。
- 限制是二元的，则以边为限制
- 元素只出现在至多两个限制中，则点是限制
有一些例子，比如网格图可以将行/列作为元素，网格图上一个点连接了对应的行列。
分数二分性质：对于所有分母 \(\le n\) 的真分数 \(val\)，其 \(\lfloor n^{2}val \rfloor\) 互不相等。
证明考虑任意两个这样的分数相减绝对值都 \(\ge \frac{1}{n^2}\)。
特殊情形下分治求颜色段算法的纯根号分析。
solve(l,r) 时，如果当前区间全部同色就返回，否则递归进两个儿子。
如果 \(c_i\le \lfloor \frac{n}{i} \rfloor\)，那么这个算法的复杂度是 \(O(n\sqrt{n})\) 的。
//可以补充其他的常见根号算法。
在 dp 解决最优化问题的时候就考虑某个方案在今后优不优，会不会被谁完全偏序；
解决计数问题时则考虑某两个方案在未决策部分是否能被区分。
前缀和 max 有两种求法。
法一：从前往后扫描，记录 \(sum,max\) 两个变量。
法二：从后往前扫描，只记录 \(max\) 一个变量即可。因为开头加一个数对前缀和的影响是整体的。
有个相关的 trick 理论上是要放到转置原理专题去的，但是不知道咋写，就先放这了。
给出一个概率序列，\(p_i\) 表示点 \(i\) 是 \(1\) 的概率，反之是 \(0\)。对于其每个前缀求出：这个前缀的前缀和 max 的期望值。
正确的 dp 方向是从后向前，但是我们又要求每个前缀，这很困难。
因此考虑转置原理即可轻易反转计算过程。
线段树合并优化 dp 可以支持的转移有很多，有一种比较 tricky 的是让原有的和新来的之间有大小关系限制的相互贡献。
具体做法就是，考虑合并两个节点 \(u,v\) 的时候，将 \(u\) 的左子树和 \(v\) 的右子树信息进行合并贡献，反之亦然。
//这里也应当有例题，后面再找。
单调性与凸性
在线完全决策单调性——简化 LARSCH 算法。
划段函数是四边形不等式的情况下，权值关于所划段数有凸性。
凸性相关知识点：
- 斜率优化、凸包、二维凸性
- 凸共轭
- 维护函数最值（KTT，李超线段树）
- 费用流、贪心、反悔贪心的凸性
- 点集整体刻画（闵可夫斯基和）
凸性的来源：
- 方案间的平均（集合/连通块的调整/拼接）
- 整体刻画，整体统计（dp）//没懂是啥
- 套特定模型（贪心）//不太有通解
- 连续性（切点，例子是要求黑边条数为某值的最小生成树）//这太难了无法理解
//这一段非常需要补充例题，否则实在是空中楼阁。
单调区间：满足如果 \(L \le l \le r \le R\)，则 \(f_{l,r} \le f_{L,R}\) 的区间权值（反之亦然）。
刻画方式：可以考虑上二维平面，然后观察其等价类折线（由同一权值的区间组成的形状）。