- 「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。
我们可以归纳证明 fi(x) 是凸的：第一个操作是加上两段斜率为 ±1 的直线，第二个操作是把斜率 >0 的部分砍掉。
证明的过程已经给出了算法：维护拐点的多重集，其中出现次数表示此处斜率变化的大小。注意到我们每次转移后永远在最后一段有斜率为 0，因此插入两个 ai+1 后弹掉最大的拐点即可。
「ABC217H」Snuketoon
令 fi(x) 表示经过 i 个事件，Snuke 在 x 点受到的最小伤害。
需要注意到我们有定义域 [−Ti,Ti]。
转移是 fi(x)=min|x′−x|≤Ti−Ti−1fi−1(x′)+gi(x)，其中 gi(x) 是一条射线。
我们将正负斜率部分分开维护，注意到区间 min 相当于将两部分分别向左和右平移 Ti−Ti−1 单位，然后加一条不影响凸性的射线。
「CF1534G」A New Beginning
可以先将 Chebyshev 距离转 Manhattan，也可以不做。
考虑直接做 Chebyshev，显然恰好是 X+Y=xi+yi 的时候才会标记 (xi,yi)。
设 fk(x) 为走到了 (x,k−x)，已经标记了所有 xi+yi≤k 的点的最小总能量。
转移是 fk(x)=min{fk−1(x−1),fk−1(x)}+gk(x)，其中 gk(x) 是若干个 |x−xi| 的和。
从而就是将斜率为正的部分向右平移 1 单位，然后加一些射线。
「ARC070E」NarrowRectangles
设 fi(x) 表示操作了 1,…,i，最后 li=x 的最小代价。
转移是 fi(x)=minx−ri−1+li−1≤x′≤x+ri−lifi(x′)+|li−x|。
仍然是分斜率正负的平移，然后加两条射线。
「CTSC2009」序列变换
和前面的题差不多，但是它限制了定义域，所以在截取的时候可能需要将谷底平移并修改维护的答案，实现较为麻烦。
也可以直接构造方案然后求答案。
「APIO2016」烟火表演
设 fu(x) 表示操作了 u 的子树，其中所有叶子到 u 的距离均为 x 的最小代价。
考虑转移是 fu(x)=∑vminx′≤x{fv(x′)+|x−x′−w|}，其中 ∑v 通常是容易的，minx′ 即 fv(x) 与 |x−w| 做 Minkowski 和。
将斜率归并，那么 <0 的斜率依然在最前面，<0 与 =0 之间会插入一条横向长度为 w，斜率为 −1 的直线，>0 的直线会被删除并直接加入一条斜率为 1 的直线。
用可并堆维护即可。
「CodeChef TREEBAL」Tree Balancing
上一题的加强版。现在有费用 ci 并且可以改成负数，相当于丢掉所有斜率绝对值超过 ci 的拐点，然后整体向右平移 wi 单位。
需要使用平衡树维护。
「CF1229F」Mateusz and Escape Room
三分 n,0 之间传递的流量，然后使用 slope trick。
转移也是平移，现在我们要查询特定点的值，显然也只需从谷值开始计算贡献。
「CF280E」Sequence Transformation
和先前的题区别是费用变成了二次函数，那么我们需要在差分数组上增加一个一次函数。
需要用平衡树维护。
「CF573E」Bear and Bowling
设 fi(x) 表示前 i 个数选了 x 个的最大答案，有转移 fi(x)=max{fi−1(x),fi−1(x−1)+aix}。
归纳证明凸性。考虑转移，选择后者当且仅当某一处 fi−1(x)−fi−1(x−1)<aix。根据归纳假设，这一部分是凸的。因此转移就是在差分数组中找到第一个需要选择后者的位置 x′，插入一个 aix′ 并将后面的部分加上 x′。
用平衡树维护。
「USACO 2021.1 Platinum」Minimum Cost Paths
设 fy(x) 表示走到 (x,y) 的最小代价。转移是首先加上 x2，然后在差分数组中插入一个 cy。
其实这就是 L2 保序回归，这个做法跟单调栈做法本质相同。
「BZOJ4877」跳伞求生
老鼠进洞！
设 fi(x) 表示前 i 个点，有 x 组匹配要经过 (i,i+1) 的最大费用。
如果是一个费用为 w 的老鼠，那么转移是 fi(x)=max{fi−1(x),fi−1(x−1)+w}。相当于在差分数组中插入一个 w。
如果是一个费用为 w 的洞，那么转移是 fi(x)=max{fi−1(x),fi−1(x+1)+w}。相当于将差分数组中第一个位置删除并插入一个 −w。
其实跟反悔贪心一模一样。
「CTSC2010」产品销售
注意方向不同的匹配必然不会相交，方向相同的匹配是否相交并不重要，我们只关心流量。
设 fi(x) 表示最终 (i,i+1) 的流量为 x（若 x<0 表示向左流），1,…,i+1 之间的边的最小总费用。由费用流建模，可以证明其 ≥0 与 ≤0 部分均是凸的。
设其差分数组
gi(x)={fi(x)−fi(x−1),x>00,x=0fi(x)−fi(x+1),x<0
另设辅助函数
hi(x)={−Mix,x>00,x=0Cix,x<0
则也可证明 (fi+hi)(x) 整体是凸的，因为这等价于删除 (i,i+1) 的费用。
首先考虑从 i−1 到 i，我们需要
fi(x)={fi−1(x)+Mix,x>0fi−1(0),x=0fi−1(x)−Cix,x<0
这就是差分数组的整体加。
考虑现在 i 处加入了一条入边，有转移
f′i(x)={min{fi(x),fi(x−1)+Pi+Mi},x>0min{fi(x),fi(x−1)+Pi−Ci},x≤0
然后令 fi(x)←f′i(x)。
若 gi(−1)≥Ci−Pi，则 gi 的 x<0 部分不变，x>0 部分等价于插入 Pi+Mi。
若 gi(−1)<Ci−Pi，则对于 x<0 部分等价于删除 gi(−1) 后插入 Ci−Pi。对于 x>0 部分，f′i(0)=fi(0)+gi(−1)+Pi−Ci，而由 (fi+hi)(x) 的凸性（容易说明完成转移之前也是凸的），有 fi(0)−fi(−1)+Ci≤fi(1)−fi(0)−Mi 即 fi(1)≥fi(0)+Mi+Ci−gi(−1)>fi(0)+Mi+Pi，因此 f′i(1)=fi(0)+Mi+Pi，且 g′i(1)=−gi(−1)+Mi+Ci。因而相当于在 x>0 部分插入 −gi(−1)+Mi+Ci。
要支持批量加入与删除，需要使用平衡树维护。
「2018 ICPC World Finals」Conquer The World
注意到子树的合并即 Minkowski 和，使用可并堆维护即可。
「2023 Multi-University Training Contest 3」Teyberrs
细节比较多，但总体来说还是先前的基本操作的组合。
此题可以用线段树维护。
「THUPC 2024 初赛」一棵树
双倍经验：「Yuhao Du Contest 7」Cyclic Distance。
设 fu(x) 表示 u 子树内选 x 个黑点的答案。合并是 Minkowski。
标算是维护两部分可并堆，但是 Treap / Splay 等能支持在树上 O(nlogn) 合并的平衡树常数足够优秀也可以通过。