何为斜率优化

对于一类动态规划问题,方程式诸如

$$
f_i=\max\{c_i + k_i \cdot x_j + y_j | j \lt i\}
$$

朴素的 $dp$ 做法的时间复杂度是 $O(n^2)$ 的,可以利用这个方程的一些特殊性质达到 $O(n \text{log}n)$ 乃至 $O(n \text{log}^2n)$

从改写方程开始

$$
f_i=\max\{c_i + k_i \cdot x_j + y_j | j \lt i\}
$$

可以改写为

$$
-k_i \cdot x_j + f_i - c_i = y_j
$$

这个式子的意义是一条斜率为 $-k_i$ ,过点 $(x_j,y_j)$ ,截距为 $f_i-c_i$ 的直线

此时目标是最大化 $f_i - c_i$ ,由于 $c_i$ 是定值,原目标等价于最大化 $f_i$

维护点集和获取最大值

那么现在需要维护一个点集 $(x_j,y_j)$ ,每当处理完 $f_i$ 后就需要将 $(x_i,y_i)$ 加入点集

显然使得$f_i$取得最大值的点是在点集的凸壳上,所以要维护一个凸壳

查询使得$f_i$最大的点的时候,是用的一条斜率固定的直线去切这个凸壳,可以通过二分斜率或者凸壳上三分查询

常用的维护套路

加入的点的$x$递增,查询的斜率递增

这是最普通的斜率优化的形式

回忆静态凸壳的构造方法:按照$x$排序后依次添加并维护凸性

那么由于点的$x$递增,用这种方法维护就行

由于查询的斜率是递增的,那么相当于直线一直在某时针旋转,同时加入的点的$x$递增,显然决策递增,可以用单调队列维护

加入的点的$x$递增,查询的斜率不保证递增

点还是原先的加入方法就行,但是斜率不一定递增了

那么直接在凸壳上二分或三分就行了

加入的点的$x$不保证递增,查询的斜率递增

点的加入需要用std::set等进行维护了,查询的话也需要二分或三分了

$x$和斜率都不保证递增

二进制分组

维护log个凸壳,大小分别为$x,\frac{x}{2},\frac{x}{4},\cdots$(虽然这么表述有些不严谨,但是可以类似的意会一下),其中$x$表示最大的那个凸壳,这些用一个vector来存储,大小递减

当添加一个新的点后,放到vector的尾部,并比较最后两个凸壳的大小是否相等,相等的话就暴力弹出这两个凸壳并将它们暴力合并,合并完后再放入vector尾部

查询的话在每个凸壳上二分或三分即可

可以证明时间复杂度是$O(n \text{log}^2 n)$

cdq分治

嘛,这个就说来话长了

首先开一个结构体,记录一下$i,k_i$,分别表示计算第$i$个$f$(这里$i$表示$id$),用到的斜率为$k_i$

然后按照$k_i$将结构体排序

定义cdq(l,r)表示计算所有$l \le i \le r$的$f_i$

那么执行完$cdq(1,n)$之后就完成任务咯

那么假设执行了cdq(l,r),不妨先根据$mid=\lfloor \frac{l+r}{2} \rfloor$将下标为$[l,r]$的结构体分开计算

先把所有$id \le mid$的分成一波,另外的分成一波,这个操作要在原序列上进行

分割完之后,结构体的$[l,mid]$中的元素的$id$都是$\le mid$的,此时先递归一下cdq(l,mid)

假设cdq(l,mid)递归完之后,这些元素所表示的点集都已经排好序了

由于在最开始的时候已经按照$k_i$排序了,所以$[mid+1,r]$实际上斜率是递增的

那么用$[l,mid]$的点构建凸包后,只需要用单调队列扫一遍更新就好咯?因为这里用的$[l,mid]$中的点去更新的$[mid+1,r]$

更新完之后在调用一下cdq(mid+1,r)就完成任务咯?

不不不,别忘了需要保证计算完cdq(l,r)之后,$[l,r]$的点集已经排好序了

发现$[l,mid]$和$[mid+1,r]$分别都排好序了,那么归并排序一下就好咯?

时间复杂度$O(n \log n)$

也许看一下代码比较好理解

平衡树/std::set

二进制分组可以支持在线查询$f_i$,但是时间复杂度比较高

cdq分治可以支持复杂度较小的查询$f_i$,但是需要离线

如果强制在线的查询$f_i$呢?

用平衡树来维护凸壳,并在上面二分!

甚至你可以用std::set