这里并不是在详细地介绍斜率优化，只是一些瞎扯，想真正系统学习斜率优化的话请去阅读其他文章。
斜率优化是众多 dp 优化方式中较为常见的一种，让我们不妨回忆一下它的形式：
\[dp(i)=\min/\max(a(i)\times b(j)+c(i)+d(j)+C) \]上式中，\(a,b,c,d\) 分别为只跟 \(i\) 或 \(j\) 相关的函数，\(C\) 是一个与 \(i\) 和 \(j\) 都无关的常量。
对于此类转移，传统的优化方式通常是将每个决策点看作二维平面上的一个点，维护一个上/下凸壳，将每次转移看作是一条直线去切这个凸壳，求出第一个切点并转移。
而维护的方式也需要根据题目的不同来改变，比如：
- 当每次转移对应的直线斜率 \(k\) 和每次加入点的横坐标 \(x_i\) 都是单调递增的时，我们可以直接使用一个单调队列维护凸壳，每次转移直接踢掉不优的决策点后取出队头即可。
- 当每次转移对应的直线斜率 \(k\) 不再单调，但是每次加入点的横坐标 \(x_i\) 还是单调的时，我们还是可以使用单调队列维护凸壳，但是转移时我们需要通过二分找出最优决策点。
- 如果两者都不单调，那么我们需要使用平衡树或 CDQ 分治的方式来维护凸壳，每次转移也需要二分来寻找切点。
这么多种情况，使得我们在实现的时候需要仔细考虑凸壳的维护方式，并且维护凸壳过程的本身就需要很多的讨论与细节，而且凸壳的具体形状也是我们必须要考虑的。
事实上，我们有一个更普遍的做法——使用李超树，不再去维护凸包，转而将每个决策点看作一个一次函数。
具体地，回到上面的式子，我们将只和 \(i\) 相关的项和常量分离出来，写成下面这样：
\[dp(i)=\min/\max(b(j)\times a(i)+d(j))+c(i)+C \]发现了没有？每个决策点 \(j\) 都可以看作是一条斜率为 \(b(j)\)，截距为 \(d(j)\) 的一次函数，转移相当于是求多个一次函数在某点上的最值。
使用李超树的优势还是很多的，不需要动脑子考虑那么多的东西，实现起来比较简单粗暴，也少了很多繁杂的推式子的过程。而且对于斜率优化问题，我们使用李超树一般直接维护直线即可，因此复杂度是一个 \(\log\) 的，代码难度和细节比平衡树和 CDQ 分治大概也要低很多。综上所述，对于斜率优化问题直接无脑上李超树维护也是一个很好的选择。
于是我直接尝试使用李超树写了两道之前做过的斜率优化题，表现很好，有空立马来补上。
标签：杂谈,斜率,凸壳,维护,优化,转移,李超树 From： https://www.cnblogs.com/los114514/p/17785792.html