单调队列总结
ATION001
·
·
个人记录
不得不说，这玩意是真的烧脑。我至少学了三遍才学会。
我们先看一道题：
P1886 滑动窗口 /【模板】单调队列
作为一名 OIer，我们肯定是优先上暴力大法（暴力该怎么写不用我说了吧）。
我们先拿单调栈试试（数据：1 3 -1 -3 5 3 6 7，区间长度为 3，先找最大值）：
$3$ 入栈，栈变为 $[1,3]$。
$-1$ 入栈，栈变为 $[-1]$（这还是求最大值吗？）。
$-3$ 入栈，栈变为 $[-3]$。
$5$ 入栈，栈变为 $[-3,5]$。
$3$ 入栈，栈变为 $[-3,3]$（这是区间吗……）。
$6$ 入栈，此时我们现在遇到了一个问题：怎么把 $-3$ 扔出去。
到了这里，你应该就能发现，栈由于本身容器的限制，无法方便地实现窗口最值查询（当然如果你能用单调栈做出来那必须 Orz）。
因此我们考虑使用队列进行维护，准确来说是双端队列。
STL 双端队列（`deque`）使用方法（局部）：
|成员函数|功能|
|:-:|:-:|
|`deque<int>q`|定义一个 `int` 类型的双端队列 $q$|
|`q.size()`|返回双端队列中的元素数量|
|`q.empty()`|判断队列是否非空，为空返回 `true`，否则返回 `false`|
|`q.front()`|返回队列的队头元素|
|`q.back()`|返回队列的队尾元素|
|`q.clear()`|将队列清空|
|`q.pop_front()`|从队头弹出一个元素|
|`q.pop_back()`|从队尾弹出一个元素|
|`q.push_front()`|从队头压入一个元素|
|`q.push_back()`|从队尾压入一个元素|
接下来我们手动模拟一个求区间最大值（区间长度为 $3$）的单调队列：
数据：`1 3 -1 -3 5 3 6 7`。
$1$ 进队，队列变为 $[1]$。
$3$ 进队，$1<3$，队列变为 $[3]$。
$-1$ 进队，$-1<3$，队列变为 $[3,-1]$。
$-3$ 进队，$-3<-1$，队列变为 $[3,-1,-3]$。
$3$ 的范围越界，队列变为 $[-1,-3]$；$5$ 进队，队列变为 $[5]$。
$3$ 进队，$3<5$，队列变为 $[5,3]$。
$6$ 进队，队列变为 $[6]$。
$7$ 进队，$6<7$，队列变为 $[7]$。
模拟结束。
如果这不够形象的话就看看题目提供的图吧：
$$\def\arraystretch{1.2}
\begin{array}{|c|c|c|}\hline
\textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline
\verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline
\verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline
\verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline
\verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline
\verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline
\verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline
\end{array}
$$
单调队列在算法竞赛中主要有两个应用点：
1. 求解**固定长度**的区间最值。
2. 优化动态规划转移过程。
Q：单调队列是否适用于所有类型的数据？
A：不是的。单调队列主要能处理有这几种特点的数据：
1. 有序性。单调队列适用于具有潜在单调性趋势的数据序列。比如在滑动窗口问题中，数据是按照一定的顺序（如数组的索引顺序）排列的，并且窗口内的数据元素之间存在大小比较关系。如果数据是完全无序的，并且没有明显的顺序可以利用来建立单调性，那么单调队列就不太适用（也就是说你很难找到数据之间的比较方式）。
2. 数据规模较大。如果某道题，$1\le n\le 10^4$，要你求出某一段的区间最值。用暴力枚举就能做，那么用单调队列做就有点“大炮打蚊子——大材小用”的感觉了。
3. 最值查询问题。单调队列非常适合用于求解区间最值问题，如果是求和，求异或和，求最大公因数等其他方面的问题，单调队列就不太适用了（当然我没说不可以用）。
好了，回归正题，我们现在该解决的问题是：P1886 该怎么解决？
~~不是吧到了这里应该会写 P1886 了吧。~~
我们维护两个单调队列，一个用来维护区间最小值，一个用来维护区间最大值。
主要步骤如下：
1. 将已经超出区间范围的元素从队头弹出。
示例：
```cpp
while(q.size()&&q.front()+m<=i){
q.pop_front();
}
```
3. 从队尾开始，如果队尾元素大于/小于当前元素的值，那么从队尾弹出元素：
示例（维护区间最小值）：
```cpp
while(q.size()&&a[q.back()]>=a[i]){
q.pop_back();
}
```
4. 从队尾压入当前元素：
示例：
```cpp
q.push_back(i);
```
>忠告：**在查询/删除容器中的元素之前，一定要判断容器是否非空**，否则在赛场上 RE 了别怪我没提醒你……而且**建议大家在判断队头元素是否在区间范围内时，从减法判断转化为加法判断**。因为有些题要开 `unsigned long long` 才能过，此时用减法判断就有可能出错。
### 实现
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,t,a[1000005],X;
deque<int>qmin,qmax;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
while(qmin.size()&&qmin.front()+m<=i){
qmin.pop_front();
}
while(qmin.size()&&a[qmin.back()]>=a[i]){
qmin.pop_back();
}
qmin.push_back(i);
if(i>=m){
cout<<a[qmin.front()]<<' ';
}
}
cout<<'\n';
for(int i=1;i<=n;i++){
while(qmax.size()&&qmax.front()+m<=i){
qmax.pop_front();
}
while(qmax.size()&&a[qmax.back()]<=a[i]){
qmax.pop_back();
}
qmax.push_back(i);
if(i>=m){
cout<<a[qmax.front()]<<' ';
}
}
return 0;
}
```
## P8661 [蓝桥杯 2018 省 B] 日志统计
挺简单的，甚至都不需要比较……
我们先将点赞记录按照时间从小到大排序，然后遍历每个点赞记录。
如果点赞记录对应的帖子还不是“热帖”，那么我们先将对应的单调队列中的无用元素（时间超过限制）弹出，然后将新纪录压入单调队列中，如果此时单调队列中的元素大于等于 $K$，说明这个帖子成了“热帖”，标记答案。
### 实现
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k,d;
deque<int>q[100005];
pair<int,int>a[100005];
bool ans[100005];
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>d>>k;
int maxid=0;
for(int i=1;i<=n;i++){
cin>>a[i].first>>a[i].second;
maxid=max(maxid,a[i].second);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(!ans[a[i].second]){
while(q[a[i].second].size()&&a[i].first-q[a[i].second].front()>=d){
q[a[i].second].pop_front();
}
q[a[i].second].push_back(a[i].first);
if(q[a[i].second].size()>=k){
ans[a[i].second]=true;
}
}
}
for(int i=0;i<=maxid;i++){
if(ans[i]){
cout<<i<<'\n';
}
}
return 0;
}
```