Preface

三年前的四月，第一次接触 OI。初三下，小教室里听着 fcx 讲着滑动窗口单调队列，放学后去本部蹭了第一节斜率优化的课，随即拉开了我长达两年的竞赛摆烂之旅。

记忆犹新。第一个注册的 OJ 账户就是 POJ，第一道 AC 的题便是 POJ 2823 滑动窗口。

多年过去，今天再看这个基础中的基础，茫然。只能说这是究极摆烂的下场罢。总之就好好写一下题解。

题面

https://www.luogu.com.cn/problem/P1886

题解

接下来只讨论求最小值的情况。设 $f[i]$ 代表终止于位置 $i$ 的滑动窗口的最小值：

$$
f[i] = \min_{i - k < j \leq i} a[j]
$$

如果暴力做的话时间复杂度为 $O(n^2)$。这里我们需要使用单调队列来优化。

对于最小值：单调队列内的元素值递增，同时 index 也是递增的。为什么这样做？思考一个情况：index 递增的情况下，如果一个 $a[i] > a[j], i < j$，那么在 $i,j$ 都有效的范围内，$a[i]$ 永远不可能作为答案。

这里有一句经典的话：如果一个选手年龄比你小，但却比你强，那你就可以退役了。我们把 index 比作出生年份，$a[]$ 比作能力，那么这句话就维护了一个求最大值的单调队列。

接下来是代码中需要注意的一些问题：

• head, tail 不是左闭右开，而是 $[head, tail]$。这样做的原因是访问 head 和 tail 的元素就可以简单的：q[head], q[tail]
• 队列里存的是 index （pos）

注意：第二个 while 可以修改为 if，因为每次 i ++ 且 q 内的 pos 递增，写成 while 是习惯。

代码

#include <iostream>

using namespace std;

const int maxn = 1e6+5;
int n, k, a[maxn], q[maxn], head, tail;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    // min
    head = 1, tail = 0;
    for (int i = 1; i <= n; i ++) {
        while (head <= tail && a[i] <= a[q[tail]]) tail --;
        q[++ tail] = i;
        while (head < tail && q[head] <= i - k) head ++;
        if (i >= k) cout << a[q[head]] << " ";
    } cout << endl;
    // max
    head = 1, tail = 0;
    for (int i = 1; i <= n; i ++) {
        while (head <= tail && a[i] >= a[q[tail]]) tail --;
        q[++ tail] = i;
        while (head < tail && q[head] <= i - k) head ++;
        if (i >= k) cout << a[q[head]] << " ";
    } cout << endl;
    return 0;
}