参考资料：
以下学习笔记为25.3.27重制版。
引入
我们先以一道题P3195 玩具装箱为例。
大概说一下题意：
我们要把一个长度为 $n$ 的数组 $a$ 分成若干段。
设一段为 $a_{l..r}$，那么其“长度”为 $r-l+\sum\limits_{i=l}^r a_i$，下面简称为 $len$。
那么这一段的“代价”为 $(len-L)^2$，$L$ 是题目中给的定值。
最后的总代价为每一段的代价的和，问最小的总代价。
暴力DP
根据题目我们能很容易设计出一个一维DP，$d_i$ 表示 $a_{1..i}$ 的划分方案最小代价，且最后一段结束位置为 $i$。
那么 $d_i=\min{d_j+w(j+1,i)}$，其中 $w(l,r)$ 为 $[l,r]$ 的代价。
转化
设 $s$ 为 $a$ 数组的前缀和，同时下面统一省略掉 $\min$，因为关于求最小值最大值只在最后一步出现。
展开之后也就是：
$$d_i=d_j+(i-j-1+s_i-s_j-L)^2$$
把括号内的东西改成只和 $i$、$j$ 相关的两部分，也就是：
$$d_i=d_j+((i+s_i)-(j+1+s_j+L))^2$$
那么我们可以设前半部分为 $a_i$，后半部分为 $b_j$，也就是：
$$d_i=d_j+(a_i-b_j)^2$$
展开：
$$d_i=d_j+a_i^2+b_j^2-2a_ib_j$$
逼近斜率优化
接下来关键的一步来了，我们考虑把上述式子移个项：
$$d_j+b_j^2=2a_ib_j+d_i-a_i^2$$
显然上面这个式子的先后顺序是我故意排的，那么我们一眼丁真一下，设：
- $y_j=d_j+b_j^2$
- $x_j=b_j$
- $k_i=2a_i$
- $b_i=d_i-a_i^2$
那么上式可以变成：
$$y_j=k_ix_j+b_i$$
数形结合
显然当我们枚举 $i$ 的时候，$i$ 就相当于是一个定值（为啥加粗下面你就知道了），那么 $k_i$ 也是定值。
同理，前面转移完后，$x_j$、$y_j$（$j<i$）都是定值。
就差 $b_i$ 是我们不知道的，也是我们要最小化的值。
所以其实问题就是说给你一些点 $(x_j,y_j)$：
然后给你一个固定的斜率（以 $k=3$ 为例，看那条灰色的直线）：
让你求出最小的截距使得它能够过任意一个点：
为了求这个值，我们需要引入一个概念叫“凸包”。
其实这个定义很直观，就是能够“包住”所有点的一个给定点组成的多边形：
而“凸包”的“下半部分”也就是“下凸壳”，就像这些线段连起来的点：
具体而言，对于一个“下凸壳”，其按照 $x$ 坐标从左到右排序的节点序列，相邻两个点之间的斜率必然是递增的。
而正是因为这些原因，我们可以发现，其实最后的答案就是和下凸壳相切的那条线的截距。
并且，其实我们很容易证明，如果我们将(下凸壳内斜率 $<$ 给定斜率)的边删掉，最后没被删的第一条边的左端点就是答案。
如下图所示：（灰色是被删除的边，红色是最后答案点，蓝色是没被删的边）
于是，一个非常基本的做法就诞生了。
“双递增”斜率优化
在P3195里面，有：
- $y_j=d_j+b_j^2$
- $x_j=b_j=j+1+s_j+L$
- $k_i=2a_i$
- $b_i=d_i-a_i^2$
我们可以发现：
- 加入的点的 $x_j$ 是单调递增的。
- 每次查询的 $k_i$ 是单调递增的。
第一条就意味着，我们每次添加的点必然是在更加右边的位置的，于是我们可以这么搞：
定义一个单调队列，维护一个斜率单调递增的下凸壳，如下图所示：
随后，如果我们要加入一个点：（红色的那个是要加入的）
结果我们发现斜率不递增了：（看绿色的那两条边）
所以我们就把队尾弹掉（这里不选择移除 $i$ 点是因为显然如果移除了就不是下凸壳了）：
继续比较：
弹出：
终于满足条件了：
于是一次节点添加就完成了。
而由于查询斜率递增，所以我们每次都不断弹出开头小于查询斜率的节点即可。
最后实现就是：（设 $q_{h..t}$ 为单调队列）
- 首先，如果队列大小大于等于 $2$ 且 $\text{slope}(q_h,q_{h+1})<k_i$，那么就直接弹出队首。
- 其次，以 $q_h$ 作为转移点转移 $d_i$。
- 然后，如果队列大小大于等于 $2$ 且 $\text{slope}(q_{t-1},q_t) \geq \text{slope}(q_t,i)$，那么就直接弹出队尾。
- 最后，在队尾加入 $i$。
相似的还有二维斜率优化，非常相似，这里就不多赘述了。
（参考代码：M2515）
如果x不递增但k递增
那么我们就要对插入做个手脚了。
这会我们插入不一定是在结尾了，可以是任何位置。
所以我们可以用set维护所有单调队列上的点。
然后我们二分一下插入位置。
随后在插入后，分别删除一下插入位置前后的几个节点，直到满足要求。
剩下的不变。
如果x递增但k不递增
因为 $x$ 递增，所以插入不变。
因为 $k$ 不递增，所以我们不能弹出队首了，而是我们要每次二分一下。
我们二分出斜率大于等于查询斜率的线段中最左边的那个，此处建议用手写队列。
剩下的不变。
“双不递增”斜率优化
但如果说两个都不递增呢？
这个有很多种做法。
【未实践】用set（唯一真神）
set（唯一真神）那么我们就考虑把上面两个做法合并一下。
我们在插入的时候维护两个set，一个记录 $(x,y)$，另一个维护相邻两个点的斜率。
查询的时候对第二个set二分即可。
理论可行，但写代码的时候需要注意很多细节。
不过复杂度是单 $\log$ 的，这是它相对于下面做法的优势。
李超线段树
我们回到上面的式子：
$$d_i=d_j+a_i^2+b_j^2-2a_ib_j$$
这时候我们换个角度思考，我们不把 $i$ 看成常量，而是换种方式转化公式：
$$d_i=-2b_j \times a_i+d_j+b_j^2+a_i^2$$
对于每个 $j$，我们加一条斜率为 $-2b_j$、截距为 $d_j+b_j^2$ 的直线。
然后在 $i$ 转移的时候，我们查一下 $x=a_i$ 的时候，最大的 $y$ 是多少，加上 $a_i^2$ 就是 $d_i$ 的最大值。
关于李超线段树可以看我的另外一篇笔记。
CDQ分治
【下面内容还要修改，咕咕咕】
初始化
在这种情况下，我们就要用到CDQ分治了。
我们直接给 $d$ 数组赋初值，并记录初始每个点的X坐标和Y坐标（还有下标），赋值到一个数组 $q$ 里去，然后把 $q$ 数组按 $s_i$ 从大到小排序。
设计CDQ函数
然后我们考虑设计 $\text{cdq}(l,r)$ 函数。
首先，如果 $l=r$，那么此时 $d_l$ 的值就知道了，所以我们就用新的 $d_l$ 值重新更新 $q_l$ 的X、Y坐标。
否则，我们求出 $[l,r]$ 区间的中点 $\text{mid}$。
然后，我们把 $q_l \sim q_r$ 内所有的 $q_i$ 按照其原本下标值（设为 $q_i . \text{id}$）分组：把满足 $q_i . \text{id} \leq \text{mid}$ 的分成一组，依次赋值到 $q_l \sim q_{\text{mid}}$；另一部分，即满足 $q_i . \text{id}>\text{mid}$ 的分成一组，依次赋值到 $q_{\text{mid}+1} \sim q_r$。
由于我们在下面计算时，需要用到 $q_l \sim q_{\text{mid}}$ 的真实X、Y坐标，所以要先递归 $\text{cdq}(l,\text{mid})$。
然后，我们考虑 $d_l \sim d_{\text{mid}}$ 对 $d_{\text{mid}+1} \sim d_r$ 的影响。
我们先对 $d_l \sim d_{\text{mid}}$ 用上述方式（斜率优化模板）建一个凸壳，用一个队列 $\text{que}_{h \dots t}$（名称为 $\text{que}$，队首下标为 $h$，队尾下标为 $t$）存起来。
我们再循环 $i=\text{mid}+1 \sim r$，然后看如果 $q_h$ 比 $q_{h+1}$ 要劣，删除 $q_h$。
弹出所有无用状态后，直接用 $q_h$ 更新 $d_i$ 即可。
执行完转移后，递归 $\text{cdq}(\text{mid}+1,r)$。
但要注意，可以维护凸壳有且仅当X坐标递增，所以此处要拿 $l \sim \text{mid}$ 和 $\text{mid}+1 \sim r$ 的排序结果，把 $q_l \sim q_r$ 内所有元素按X坐标递增顺序排序。
（参考代码：M2590）