学习笔记#5：单调队列优化&斜率优化

单调队列

首先要搞懂什么是单调队列。

单调队列是一种求区间最值问题的一种方式，与其他 RSQ 问题的求解方法不同的是，它更善于解决滑动窗口式的 RSQ 问题，一般来说，假设我们要维护最大值，则需维护一个单调递减的队列，这样队首最大，每次取队首即可。而当队首不在我们的讨论范围中时，就将它弹出。每次便利到新元素时，从队尾依次向前弹出，知道符合单调队列的性质时再将其加入。

注意，队列维护的不是数组的值，而是下标，这样才方便确定是否满足讨论范围。

每个元素分别出入队一次，所以复杂度 \(\text{O}(n)\)。

例：P1886 滑动窗口 /【模板】单调队列

有一个滑动的窗口，大小固定，每次取窗口中的最大值：
样例：

8 3
1 3 -1 -3 5 3 6 7

建立一个单调队列，维护单调递减：

int Q[maxn], head, tail;
for(int i = 1; i <= n; i++) {
	while(head < tail and Q[head] < i - k + 1) head++;//不在讨论范围内就出队
	while(head < tail and a[i] >= Q[tail]) tail--;//维护单调递减
	Q[++tail] = i;
	if(i >= k) ans[++ca] = Q[head];
}

以上就是单调队列。

单调队列优化DP

所谓单调队列优化，指的是用单调队列优化 DP。

我们经常看到这样的式子：

\(f[i] = min(f[j] + a[i] + b[j]) (L(i) \le j \le R(i))\)

如果暴力转移就是 \(\text{O}(n^2)\) 的复杂度，对于 \(1e6\) 的数据并不友好。

这时我们用单调队列维护 \(f[j] + b[j]\) 的最值， 就可以将复杂度压到 \(\text{O}(1)\) 了。

斜率优化

引入

斜率优化其实是一种特殊的单调队列优化。

我们有时也会遇到这样的式子：

\(f[i] = max(f[j] + val(i, j))\)

其中 \(val(i, j)\) 同时与 \(i\)、\(j\) 有关，无法直接用单调队列进行优化。

例：P3628 [APIO2010] 特别行动队

设 \(f[i]\) 表示以 \(i\) 为某一段的结尾，前面总得分的最大值。转移方程显然：

\(f[i] = max(f[j] + a \times (sum[i] - sum[j])^2 + b \times (sum[i] - sum[j]) + c)\)

继续化：
\((f[i] + Asum[i]^2 - Bsum[i]) + sum[j] \times 2Asum[i] = f[j] + Asum[j]^2 - Bsum[j] + c\)
我们发现中间有个难以处理的 \(sum[j] \times 2Asum[i]\)，该怎么处理呢？

于是请出今天的主角：斜率优化。

原理

转化式子

我们把只与 \(j\) 有关的整个式子写成 \(J\)，把只与 \(i\) 有关的整个式子写成 \(I\)，于是式子变成：

\(J = 2Asum[i] \times sum[j] + I\)

不难发现这是一个一次函数，\(J\) 是因变量，\(I\) 是截距，同时我们把 \(sum[j]\) 指定为自变量，那么 \(2Asum[i]\) 就是斜率。

而我们的 \(J\) 、\(2Asum[i]\)、\(sum[j]\) 均已知，只有 \(I\) 中的 \(f[i]\) 需要求出，而要使 \(f[i]\) 最大，则要使 \(I\) 最大，即截距最大。

因此我们可以将这个决策点看做一条直线，并且要求它的截距最大。

而我们的斜率是一直增大的，那么什么样的点会有可能是决策点呢？

答案是在一个上凸包中的点。

因为如果在凸包内，截距无论如何也不会比在凸包上的点更大。

因此问题就转换成了如何维护一个上凸包。

维护凸包

首先，点的横坐标 \(sum[j]\) 单调递增，因此每次新加入的决策点都在最右侧，我们判断它在凸包上还是在凸包内即可。

那么我们维护一个单调队列，当队尾和队尾前面的点的斜率的大于新点和队尾的斜率的时，这个新点才在凸包上，否则就要一直弹队尾，直到满足要求。

对于队首，如果当前斜率 \(2Asum[i]\) 的小于队首和第二个点的斜率的，那么队首也就没用了，因为后面的点切出来的截距绝对比他大，所以出队。

至此，斜率优化的全过程已展示完毕。