- 「CF713C」Sonya and Problem Wihtout a Legend
- 「ABC217H」Snuketoon
- 「CF1534G」A New Beginning
- 「ARC070E」NarrowRectangles
- 「CTSC2009」序列变换
- 「APIO2016」烟火表演
- 「CodeChef TREEBAL」Tree Balancing
- 「CF1229F」Mateusz and Escape Room
- 「CF280E」Sequence Transformation
- 「CF573E」Bear and Bowling
- 「USACO 2021.1 Platinum」Minimum Cost Paths
- 「BZOJ4877」跳伞求生
- 「CTSC2010」产品销售
- 「2018 ICPC World Finals」Conquer The World
- 「2023 Multi-University Training Contest 3」Teyberrs
- 「THUPC 2024 初赛」一棵树
前情提要：在「模拟费用流题集」中尝试坚持非 slope trick 的原生费用流做法，受阻。
顺便声明，笔者认为对凸函数维护折线的做法都属于 slope trick，而不区分维护方式。
「CF713C」Sonya and Problem Wihtout a Legend
典中典题。从经验倍数之多就可以看出：
- 「洛谷 P4331」Sequence 数字序列
- 「洛谷 P4597」序列 sequence
- 「CF13C」Sequence
- 「USACO 2008.2 Gold」Making the Grade
首先给 ai←ai−i，然后问题限制变为不降。
我们有大力 DP fi(x) 表示操作了 1,…,i，最后 ai≤x 的最小次数。
考虑 fi−1 转移到 fi 做的事：
加上函数 |ai−x|。
做前缀 min。
我们可以归纳证明 f_i(x) 是凸的：第一个操作是加上两段斜率为 \pm 1 的直线，第二个操作是把斜率 > 0 的部分砍掉。
证明的过程已经给出了算法：维护拐点的多重集，其中出现次数表示此处斜率变化的大小。注意到我们每次转移后永远在最后一段有斜率为 0，因此插入两个 a_{i+1} 后弹掉最大的拐点即可。
「ABC217H」Snuketoon
令 f_i(x) 表示经过 i 个事件，Snuke 在 x 点受到的最小伤害。
需要注意到我们有定义域 [-T_i, T_i]。
转移是 f_i(x) = \min_{|x'-x| \le T_i-T_{i-1}} f_{i-1}(x')+ g_i(x)，其中 g_i(x) 是一条射线。
我们将正负斜率部分分开维护，注意到区间 \min 相当于将两部分分别向左和右平移 T_i-T_{i-1} 单位，然后加一条不影响凸性的射线。
「CF1534G」A New Beginning
可以先将 Chebyshev 距离转 Manhattan，也可以不做。
考虑直接做 Chebyshev，显然恰好是 X+Y=x_i+y_i 的时候才会标记 (x_i, y_i)。
设 f_k(x) 为走到了 (x, k-x)，已经标记了所有 x_i+y_i \le k 的点的最小总能量。
转移是 f_k(x) = \min\{f_{k-1}(x-1), f_{k-1}(x)\} + g_k(x)，其中 g_k(x) 是若干个 |x-x_i| 的和。
从而就是将斜率为正的部分向右平移 1 单位，然后加一些射线。
「ARC070E」NarrowRectangles
设 f_i(x) 表示操作了 1,\dots,i，最后 l_i=x 的最小代价。
转移是 f_i(x) = \min_{x-r_{i-1}+l_{i-1} \le x' \le x+r_i-l_i} f_i(x') + |l_i-x|。
仍然是分斜率正负的平移，然后加两条射线。
「CTSC2009」序列变换
和前面的题差不多，但是它限制了定义域，所以在截取的时候可能需要将谷底平移并修改维护的答案，实现较为麻烦。
也可以直接构造方案然后求答案。
「APIO2016」烟火表演
设 f_u(x) 表示操作了 u 的子树，其中所有叶子到 u 的距离均为 x 的最小代价。
考虑转移是 f_u(x) = \sum_v \min_{x'\le x} \{f_v(x') + |x-x'-w|\}，其中 \sum_v 通常是容易的，\min_{x'} 即 f_v(x) 与 |x-w| 做 Minkowski 和。
将斜率归并，那么 <0 的斜率依然在最前面，<0 与 =0 之间会插入一条横向长度为 w，斜率为 -1 的直线，>0 的直线会被删除并直接加入一条斜率为 1 的直线。
用可并堆维护即可。
「CodeChef TREEBAL」Tree Balancing
上一题的加强版。现在有费用 c_i 并且可以改成负数，相当于丢掉所有斜率绝对值超过 c_i 的拐点，然后整体向右平移 w_i 单位。
需要使用平衡树维护。
「CF1229F」Mateusz and Escape Room
三分 n,0 之间传递的流量，然后使用 slope trick。
转移也是平移，现在我们要查询特定点的值，显然也只需从谷值开始计算贡献。
「CF280E」Sequence Transformation
和先前的题区别是费用变成了二次函数，那么我们需要在差分数组上增加一个一次函数。
需要用平衡树维护。
「CF573E」Bear and Bowling
设 f_i(x) 表示前 i 个数选了 x 个的最大答案，有转移 f_i(x) = \max\{f_{i-1}(x), f_{i-1}(x-1)+a_i x\}。
归纳证明凸性。考虑转移，选择后者当且仅当某一处 f_{i-1}(x) - f_{i-1}(x-1) < a_i x。根据归纳假设，这一部分是凸的。因此转移就是在差分数组中找到第一个需要选择后者的位置 x'，插入一个 a_i x' 并将后面的部分加上 x'。
用平衡树维护。
「USACO 2021.1 Platinum」Minimum Cost Paths
设 f_y(x) 表示走到 (x, y) 的最小代价。转移是首先加上 x^2，然后在差分数组中插入一个 c_y。
其实这就是 L_2 保序回归，这个做法跟单调栈做法本质相同。
「BZOJ4877」跳伞求生
老鼠进洞！
设 f_i(x) 表示前 i 个点，有 x 组匹配要经过 (i, i+1) 的最大费用。
如果是一个费用为 w 的老鼠，那么转移是 f_i(x) = \max\{f_{i-1}(x), f_{i-1}(x-1)+w\}。相当于在差分数组中插入一个 w。
如果是一个费用为 w 的洞，那么转移是 f_i(x) = \max\{f_{i-1}(x), f_{i-1}(x+1)+w\}。相当于将差分数组中第一个位置删除并插入一个 -w。
其实跟反悔贪心一模一样。
「CTSC2010」产品销售
注意方向不同的匹配必然不会相交，方向相同的匹配是否相交并不重要，我们只关心流量。
设 f_i(x) 表示最终 (i, i+1) 的流量为 x（若 x<0 表示向左流），1,\dots,i+1 之间的边的最小总费用。由费用流建模，可以证明其 \ge 0 与 \le 0 部分均是凸的。
设其差分数组
g_i(x) = \begin{cases} f_i(x)-f_i(x-1), &x>0\\ 0, &x=0 \\ f_i(x)-f_i(x+1), &x<0 \end{cases}
另设辅助函数
h_i(x) = \begin{cases} -M_i x, & x > 0 \\ 0, & x = 0 \\ C_i x, & x < 0 \end{cases}
则也可证明 (f_i+h_i)(x) 整体是凸的，因为这等价于删除 (i, i+1) 的费用。
首先考虑从 i-1 到 i，我们需要
f_i(x) = \begin{cases} f_{i-1}(x) + M_i x, & x>0 \\ f_{i-1}(0), & x=0 \\ f_{i-1}(x) - C_i x, & x<0 \end{cases}
这就是差分数组的整体加。
考虑现在 i 处加入了一条入边，有转移
f_i'(x) = \begin{cases} \min\{f_i(x), f_i(x-1)+P_i+M_i\}, & x>0 \\ \min\{f_i(x), f_i(x-1)+P_i-C_i\}, & x\le 0 \end{cases}
然后令 f_i(x) \gets f_i'(x)。
若 g_i(-1) \ge C_i-P_i，则 g_i 的 x < 0 部分不变，x > 0 部分等价于插入 P_i+M_i。
若 g_i(-1) < C_i-P_i，则对于 x < 0 部分等价于删除 g_i(-1) 后插入 C_i-P_i。对于 x > 0 部分，f_i'(0)=f_i(0)+g_i(-1)+P_i-C_i，而由 (f_i+h_i)(x) 的凸性（容易说明完成转移之前也是凸的），有 f_i(0)-f_i(-1)+C_i \le f_i(1)-f_i(0)-M_i 即 f_i(1) \ge f_i(0) + M_i + C_i - g_i(-1) > f_i(0) + M_i + P_i，因此 f_i'(1) = f_i(0) + M_i + P_i，且 g_i'(1)=-g_i(-1)+M_i+C_i。因而相当于在 x>0 部分插入 -g_i(-1)+M_i+C_i。
要支持批量加入与删除，需要使用平衡树维护。
「2018 ICPC World Finals」Conquer The World
注意到子树的合并即 Minkowski 和，使用可并堆维护即可。
「2023 Multi-University Training Contest 3」Teyberrs
细节比较多，但总体来说还是先前的基本操作的组合。
此题可以用线段树维护。
「THUPC 2024 初赛」一棵树
双倍经验：「Yuhao Du Contest 7」Cyclic Distance。
设 f_u(x) 表示 u 子树内选 x 个黑点的答案。合并是 Minkowski。
标算是维护两部分可并堆，但是 Treap / Splay 等能支持在树上 O(n\log n) 合并的平衡树常数足够优秀也可以通过。