单调队列

求每个固定长度区间最值

顾名思义,单调队列即是一个单调的队列.

这里只考虑求区间最小值.

建立一个单调递增的队列,队首是最小值.

开始队列为空,每次添元素的时候,从队尾向前比较,

直到找到最靠前的比自己小的数,将待添加元素添加到这个数后面,

舍弃后面的所以数.(这是因为新添加的数一定比后面的数更优)

每次取最小值时,因为区间左端点在变,

故对于队列中的每一个元素,记录它在原数列中的位置.

当当前所求区间中不含队首元素时,将队首舍弃.

直到队首在所求区间时,输出队首即可.

由于每个元素最多进出队一次,故复杂度为O(n).

struct dddl{
    int queue[maxn],t[maxn],tou,wei,ji;
    void csh(){tou=wei=0;}
    void push(int e,int tim){//添加的数为e,其在原数列中的位置为tim.
        单增:if(ji==0)while(tou<wei&&queue[wei-1]>=e)wei--;
        单减:if(ji==1)while(tou<wei&&queue[wei-1]<=e)wei--;
        wei++;queue[wei-1]=e;t[wei-1]=tim;
    }
    int gettop(int tim){//tim为目前区间所含有的下标最小的数的下标.
        while(t[tou]<tim)tou++;
        return queue[tou];
    }
}que;