- 「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
首先给 \(a_i \gets a_i-i\)，然后问题限制变为不降。
我们有大力 DP \(f_i(x)\) 表示操作了 \(1,\dots,i\)，最后 \(a_i \le x\) 的最小次数。
考虑 \(f_{i-1}\) 转移到 \(f_i\) 做的事：
加上函数 \(|a_i-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)\) 合并的平衡树常数足够优秀也可以通过。