Slope Trick
这个 Trick 一百万年前就听说过了。
一直没写过笔记，直到暑假集训做了那个经典 Cyclic Distance 才想起来写。
Slope trick 应该分三种，一种是维护斜率序列，一种是维护变化点，一种是直接维护函数值，下面的例题分别对应这三种情况。
不过网上常见的博客都只提到了第一种，我个人认为它们的思想是差不多的，都归为 slope trick 了（最后一种和第一种只差一个差分所以也没啥区别）
泛化ψ(｀∇´)ψ
对于一类转移代价是凸函数的问题，如果能够证明 dp 状态也是凸函数且凸性相同（这里的凸函数定义为一阶差分单调（类似于分段一阶导））。
且通常来说，dp 都是关于阶段呈凸包状的，那么就可以考虑用 slope trick 来优化转移的过程。
具体做法是把每一个阶段的 dp 值看作一个函数，根据状态进行一些合并，平移之类的操作。
一个比较容易证明的事情是，如果我们知道 \(G,H\) 都是凸函数且凸性相同，那么如果 \(F(x) = G(x) + H(x)\)，可以得到 \(F\) 也是一个凸函数。
并且如果我们记录 \(L(F)\) 表示 \(F\) 的所有转折点（每一段最后一个整点，表示斜率变化为 \(1\)，如果变化大于 \(1\) 则重复记录）集合，可以得到 \(L(F) = L(G) \cap L(H)\)
那么只要考虑 \(L\) 序列的维护就能够很好的完成任务，当然因为我们只记了变化点位置，所以还需要记录一下开头一段的斜率和截距。
这个是 slope trick 的第一类形式（我瞎命名的，主要是几乎没见过有人把这三种凸性优化放在一起考虑过）。
还有一种形式是，我们可以不维护转折点，直接维护函数值。
也有一种形式是对函数值维护一个差分，相当于直接维护斜率序列（这种一般都是做 \(\max +\) 卷积为了方便才这么干）
例子ψ(｀∇´)ψ
CF713Cψ(｀∇´)ψ
首先暴力的方程是大家都会的。
\(dp(i, j)\) 表示考虑前 \(i\) 个数需要的最少操作次数。
所以 \(dp(i, j) = \min\limits_{k \le j}\{dp(i - 1, k)\} + |a_i - j|\)。
可以注意到代价函数是绝对值函数，它是下凸的，而且转移方程实际上是一个 dp 状态和一个下凸函数合并得到一个 dp 状态。
初始化的时候 dp 状态是一个 “0” 状态，和下凸函数合并自然得到下凸函数，以此类推可以发现 \(dp_i\) 系状态是一个下凸的函数。
不妨固定 \(i\)，考虑优化 \(i\) 的转移，即令 \(F_i(x) = dp(i, x)\)。
那么转移方程化为 \(F_i(x) = \min\limits_{k \le j}\{F_{i - 1}(k)\} + |a_i - x|\)。
不妨记 \(G_i(x) = \min\limits_{k \le j}\{F_{i - 1}(k)\}\)，可以发现，\(G_i\) 实际上是在对 \(F_{i - 1}\) 做一个前缀最小值，它也应该是具有下凸的形式的。
因为 \(F\) 是下凸函数，注意到最值应该在切线斜率为 \(0\) 的地方取到。所以 \(G_i\) 应该长成这样：
其中红色部分是 \(F_{i - 1}, G_i\) 重合的部分（因为 \(F\) 本身就下凸所以其实取前缀最小值唯一的影响是到了极值点之后会变成一个值）
然后考虑合并 \(G_i, |x - a_i|\)，可以注意到这实际上是往 \(G_i\) 里面加了两个分界点 \(\{a_i, a_i\}\)，但不止如此，我们不能光看分界点。
注意后面黄色的部分，你可以发现不管这个绝对值函数加在哪里，一定会有类似黄色的部分，换句话说 \(G_i\) 到了极值点就平了，现在又翘起来了，所以我们还需要把它按下去。
注意到实际上斜率只会从 \(\{-5,-4,-3,-2,-1,0\}\) 的形式变成 \(\{-6,-5,-4,-3,-2,-1,0,1\}\) 的形式，相当于只会多一个变化点，所以我们直接使用一个 std::priority_queue 维护变化点集合，每次加入两个弹掉位置最靠后的即可。
Mock20230721T1ψ(｀∇´)ψ
赛时（通过打表）看出了下凸但是不知道咋维护，因为当时只会做 minkovski 和的形式的 slope trick（）
这个是校内模拟赛不能放出来，如果是 cwoi 的同学应该知道密码。
方程是 \(dp(i, j) = \min\limits_{|k - j| \le d}\{dp(i - 1, k)\} + |a_i - j|\)。
通过打表可以发现（其实归纳下就好了） \(dp_i\) 系列的状态是下凸的。
后面又是个绝对值函数，于是我们考虑 slope trick 维护。
但是 \(\min\limits_{|k - j| \le d}\{dp(i - 1, k)\}\) 的部分应该怎么维护呢？
注意到实际上这就是，在 \(F_{i - 1}\) 的基础上，增加了一个长度为 \(2d\) 的斜率为 \(0\) 的段。
考虑对极值点两边分讨，只考虑左边，相当于就是每一个点变为原来在它右边 \(d\) 位置的值，那么就是把极值点两边的部分分别往外平移 \(d\) 个单位。
然后中间用一条斜率为 \(0\) 的线连接起来，截距为 \(F_{i - 1}\) 的最小值。
然后就又是合并上一个下凸函数，维护一下就好。
具体怎么维护？这里就有两种做法了。
一种是维护分界点，合并的部分是简单的，考虑一下怎么维护移动，就是每次需要额外记录极值点的位置，找到这个位置，分别做前缀减（包含这个位置）和后缀加（不包含）。
另一种是直接维护值（个人感觉更好理解），这个就相当于是区间加和插入，当然还需要离散化，我们平衡树维护就可以了。
QOJ2065 Cyclic Distanceψ(｀∇´)ψ
哪里有题直接把做法（Ailen Trick）写在题面上的啊（这就是 Du yuhao contest 吗）
还有一个几乎一样的题：Gym104128H，只是变成了两两距离而已。
做法是简单的，设 \(dp(u, i)\) 表示考虑在 \(u\) 子树当中选 \(i\) 个点最大价值。
然后转移比较类似树形背包，考虑把子树状态合并上来：
\(dp(u,i)=\max\limits_{j \le i}\{dp(u, i - j) + dp(v, j) + 2w(u, v)\times \min(j, k - j)\}\)
可以发现 \(dp\) 和后面那坨贡献都是上凸的形式。
证明的话，\(dp\) 考虑归纳即可，代价那一部分可以考虑一阶差分和二阶差分。
（这里是离散的，这个对应到连续的函数上面就是求导和求二阶导）。
然后这里就又是个 slope trick 的形式了。
不妨考虑先把代价函数和 \(dp(v, j)\) 合并，然后就是一个做 \(\max +\) 卷积的样子。
\(\max +\) 卷积是啥
是一个类似这样的东西（当然 u, v）不一定要是凸的：
1 2 3 | |
对于一个位置，这个过程就是这样配对的（大写对小写）：
1 2 | |
形式化一点就是类似 \(F(i + j) = \max\{G(i) + H(j)\}\) 的式子。
那么 \(G,H\) 的 \(\max +\) 卷积就是 \(F\)。
因为需要考虑具体的值，维护转折点会巨大麻烦，所以我们不妨考虑直接维护值。
然后对两个凸函数做 \(\max +\) 卷积其实是对两个函数形成的凸包做闵可夫斯基和。
可以注意到凸函数差分是单调的（斜率序列），那么差分之后，\(\max +\) 卷积就相当于是，从两个序列中分别选一个前缀，一共选 \(s\) 个，要求最大化前缀和。
那么这里就是对差分数组做一个归并排序取前 \(s\) 个，当然你愿意也可以用一个堆维护。
合并 \(dp(v, j), w\) 的这个过程实际上是对斜率序列两边分别做加法，平衡树维护即可。
但是还有一种方式是，注意到这个两边分别做加法只有两段（还是三段？），所以可以直接给区间整体打标记，复杂度就是对的了。