单调队列学习笔记

前言：

如果一个 Oier 比你小，还比你强，那你就不可能打败他了。 ——单调队列

准备学习基环树直径时却发现连滑动窗口都不会的蒟蒻不得不回来补笔记。

正文

单调队列

单调队列：具有单调性的队列
一般分为单调递增和单调递减，当然也有次大值。
有单调队列优化 DP 这一手，但先不在这讲（毕竟不是联赛程度的算法）

实现步骤

用单调递增队列维护一个序列 \(a\)

1. 如果队列为空，将目前元素 \(a_i\) 从队尾入队。
2. 如果队列不为空，将比目前元素 \(a_i\) 大（小）的元素从队尾弹出，然后将 \(a_i\) 从队尾入队。
3. 如果队列不为空并且 \(a_i\) 大于队尾元素，则直接将 \(a_i\) 从队尾入队。

用双端队列维护。

代码：

if(q.empty())	q.push_back(a[i]);
else{
    while(q.size()&&q.back()>a[i])    q.pop_back();
    q.push_back(a[i]);
}

先写这么点吧。