单调队列

之前听松爷扯过单调队列，于是学了一番，感受是这样的：

单调队列大法好，$O\left(n\log n\right)$变$O\left(n\right)$！

性质

单调队列，顾名思义，是一个“单调”的队列。
如何便是单调？单调递增/递减。假设下面说的都是单调递减队列。

插入元素时，如何维护单调队列的单调性？ 这是单调队列中最基础的问题。
解决方法往往很粗暴：先把队尾所有小于插入元素的都删除，然后插入元素。 这样就有序了。但是有个问题，为什么可以直接删除那些元素？

与要维护的东西的性质有关。

显然，我是懒得手打循环队列的。上STL大法——双端队列。

#include <deque>
using namespace std;

int main()
{
    deque <int> q;
    q.push_front(1);             //队首插入1
    printf("%d\n",q[0]);         //滋磁随机访问！
    q.push_back(2);              //队尾插入2
    q.push_back(3);              //队尾插入3
    q.pop_back();                //弹出队尾元素
}

例题：滑动窗口

一个长度为$n$的序列，有一个长度为$k$窗口在其中滑动。 求出：每一个位置，窗口中元素的最大值、最小值。

Example:

窗口位置                 最小值    最大值 
[ 1 3 -1 ] -3 5 3 6 7   -1      3 
1 [ 3 -1 -3 ] 5 3 6 7   -3      3 
1 3 [ -1 -3 5 ] 3 6 7   -3      5 
1 3 -1 [ -3 5 3 ] 6 7   -3      5 
1 3 -1 -3 [ 5 3 6 ] 7   3       6 
1 3 -1 -3 5 [ 3 6 7 ]   3       7 

暴力

想题先想暴力？

对于每个窗口位置，暴力求最大最小值。 复杂度$O(n\ast k)$。

平衡树

考虑优化上面的暴力。 根据滑动窗口的性质，每次移动只有一个元素进入、一个元素弹出。

由此，维护一个平衡树，储存元素的出现次数。取最大/最小值输出，窗口移动时删除左边元素、加入右边元素。

可以用STL的multiset（可重复集合）来处理。 复杂度$O\left(n\log n\right)$

单调队列

首先，我们只考虑最大值。最小值是类似的。窗口在移动，我们需要维护窗口中的最大值。

考虑下面的事实：如果有$l<i<j<r$，则如果$a_i$可选，那么$a_j$也可选。
这是很显然的。窗口在向右移动，$a_i$在$a_j$的左边，因此$a_i$比$a_j$先弹出窗口。

继续思考，如果$a_i<a_j$，因为在$a_i$可选的情况下$a_j$可选，所以一定不会选择较小值$a_i$。可以直接删除$a_i$。

那么容易想到用单调递减队列维护最大值。做法： 1. 查询。直接输出队首元素。 2. 插入右端点。根据刚才想到的性质，弹出所有小于右端点的元素，然后把右端点加入。

最棘手的问题，如何删除左端点？
我们知道如何删除堆中的元素：另建一个堆，将准备删除的元素放进删除堆；如果删除堆和原堆的堆顶相同，则各自弹出堆顶。
上面的方法的思想是，不去直接找到元素删除，而是当那个元素准备使用时删除。

推广到这个单调队列上。容易想到：有用的元素一定在$[l,r]$内。
因此，处理队首元素时，当队首元素在$[l,r]$之外，直接弹出它，直到队首元素在$[l,r]$内为止。

如何计算复杂度？每个元素入队一次、出队一次，因此处理每一个元素的复杂度是$O\left(1\right)$，总复杂度是$O\left(n\right)$。