单调队列-JZTXT

写法

首先要有一个双端队列：

struct My_dequeue{
    int hh=1,tt=0,q[N];
    void clear(){hh=1;tt=0;}
    void push_front(int k){q[--hh]=k;}
    void push_back(int k){q[++tt]=k;}
    void pop_front(){hh++;}
    void pop_back(){tt--;}
    int front(){return q[hh];}
    int back(){return q[tt];}
    int head(){return hh;}
    int tail(){return tt;}
    bool empty(){return hh>tt;}
}q;

以下给出单调队列的标准写法。

int calc(int i){//返回下标对应的值
    return inp[i];
}

void insert(int x){//传入下标
    while(!q.empty()&&calc(q.back())<=calc(x)) q.pop_back();//维护最大值
    q.push_back(x);//存入下标
}

int query(int x){
    while(q.front()<=x-k) q.pop_front();//弹出不符合条件的下标
    return calc(q.front());//返回值
}

q.clear();
for(int i=1;i<=n;i++){
    insert(i);
    ans[i]=query(i);
}

作用

维护左右端点单调的若干定长连续区间的 RMQ。

可以用于优化 DP 。要求当前状态的所有值可以从上一个状态的某个连续的段的值得到，将要对这个连续的段进行 RMQ 操作，且相邻状态的段的左右区间满足非降的关系。

具体的说，要求 DP 的状态转移方程满足以下形式（ $b$ 为任意与$k$无关的式子，$x,y$ 为任意与$j $无关的式子）：

\[f(i,j)=\max\{f(i-1,k)\}+b,k\in[j-x,j+y] \]

\[f(i)=max\{f(k)\}+b,k\in[i-x,i-y],x>0,y>0 \]

那么，就可以通过单调队列优化其时间复杂度。

具体的说，我们可以用单调队列维护上一层的 DP 数组的区间最值。由于每一层内求最值的区间长度固定，就可以仿照上面的写法将其构造成一个单调队列，计算新状态时就可以以均摊 $O(1)$ 的时间复杂度维护最值信息，这样总时间复杂度就可以少一个 $n$。是一个优秀的优化。

单调队列优化通常配合滚动数组一起适用，可以让时空均少一个 $n$。

例如：

\[f(i)=max\{f(k)\}+a[i],k\in[i-R,i-L] \]

那么代码是这样的：

int calc(int i){//返回下标对应的值
    return f[i];
}

void insert(int x){//传入下标
    while(!q.empty()&&calc(q.back())<=calc(x)) q.pop_back();//维护最大值
    q.push_back(x);//存入下标
}

int query(int x){
    while(q.front()<=x-R-1) q.pop_front();//弹出不符合条件的下标
    return calc(q.front());//返回值
}

q.clear();
for(int i=L;i<=n;i++){
    insert(i-L);
    f[i]=query(i)+a[i];
    if(i+R>n) ans=max(ans,f[i]);
}