单调队列

常见的队列一般分为两类：FIFO（先进先出）型和特定元素优先型。第一类常称作普通队列，第二类常被称作优先队列，它实际上更像是一个小根堆……

一 引入

在讲解单调队列之前， 让我们先回顾一下普通队列。

1 为什么需要单调队列

常见的队列一般分为两类：FIFO（先进先出）型和特定元素优先型。第一类常称作普通队列，第二类常被称作优先队列，它实际上更像是一个小根堆。
二者的用处也不尽相同，前者用于维护进队次序上的先入队者，而后者用来维护数值上的极大（小）者。
对于这两类，STL中都有相应的模板，常数也不是很大，而且支持的操作也很多，因此只在这里罗列一下：

//queue and priority_queue in STL
#include<queue>
using namespace std;

queue<int>Q;
Q.push(); //插入
Q.front(); //返回队首元素
Q.pop(); //出对
Q.empty(); //返回是否队空

priority_queue<int>heap;
heap.push(); //插入
heap.top(); //返回堆顶
heap.pop(); //删除
heap.empty(); //返回是否堆空

但是如果我们遇到这样一个问题：
维护一段数列，支持在末尾插入一个数据，在首端删除一个数据，和查询在某一范围内的最大（小）值。
这样，普通队列和优先队列都会黯然失色。因为普通队列仅能维护次序性而忽略了元素本身，而优先队列仅维护了元素大小关系却忽略了它们的入队次序。
这时，我们就需要单调队列。

2 什么是单调队列

正如上面的问题，单调队列就是这样的一个数据结构：
维护一段数列，支持在末尾插入一个数据，在首端删除一个数据，和查询数列的最大（小）值。

显然我们还有一种强大的数据结构可以部分替代它——为所欲为的线段树。但有时候它会跑的很慢，因为它还有一个$O(\log n)$的累赘，而单调队列是$O(n)$的。

---

二 实现

1 实现思想

那么单调队列怎么实现这些操作呢？

可以这样设想：保证队首的元素最大，这样就可以$O(1)$的查询最大值。但是，在首端删除需要维护元素的次序性，因为最大元素不一定是数列的第一个元素。又要使得这个队列内的元素单调下降，因为只有这样，才能保证首端删除后的新首端依然是最大的。

插入元素的时候该怎样维护？
不难发现，若当前队尾为$s_t$，新插入的元素为$s_k$，且队列中存在元素$s_i$满足$s_i < s_k$且$s_{i-1} > s_k$，那么$s_{i},s_{i+1},…,s_t$这一部分都是无用的，因为它们比新插入的元素小，对最大值已经没了贡献。删掉它们（这时从队尾出队），既能维护单调性，又可以维护次序性。

这样就实现了单调队列：在维护次序性的同时维护元素单调递减。

2 代码实现

const int C=1e6+6;

class mqueue{
  public:
    int d[C],key[C]; //元素的值与下标
    int head,tail; //首尾指针
    mqueue() {tail=-1;head=0;}
    
    void pop(int s) //出队，s为出队后队首的下标
    {
        while(key[head]<s && head<=tail) 
          head++; 
    }
    
    int front() {return d[head];} //返回队首
    
    void push(int v,int k) //插入： v 值; k 下标
    {
        while(head<=tail && d[tail]>v) //出队直到满足单调性
          tail--;    
        d[++tail]=v; //插入
        key[tail]=k;
    }
};