返回目录

起初，没有人注意到此blog。

单调队列，是一个有顺序的队列

它会严格保持单调性，永远都不会造反。

那么它的作用是什么呢?

它可以通过在一个区间内的单调性来寻找最值

(如果找不到区间最大/最小，就用他吧！)

具体的操作非常简单，可以概括为掐头去尾

掐头:如果要求区间长度不能超过 $m$ 那么就必须把超出长度的数据删掉！

去尾:如果新入队的数据不符合单调性(例如求区间最大值，但是新入队的数据最大) 那么就把它前面的数据删掉

别担心，它有代码模板！！！\o/\o/\o/\o/

struct node{
    int k;#该数据在数组中的值
    int id;#该数据在数组中的下标
}

deque <node> q; 

for(int i=1;i<=n;i++){
		while(!q.empty()&&a[i].k-q.front().k>=x){
        q.pop_front();
        #掐头
		}
    while(!q.empty()&&a[i].d<=q.back().d){
        q.pop_back();
        #去尾
    }
		q.push_back(a[i]);
    #将节点放入队列
}

学会了就来GF25做题吧