单调队列

· · 个人记录

一篇博客需要一个引领全文的话：

\large\text{当一个人比你小还比你强，你就该考虑退役了 ！} \small{-\ When\ someone\ is\ younger\ than\ you\ and\ better\ than\ you,\ it's\ time\ to\ consider\ retirement!\ -}

这就是单调队列的精髓。

原理：

单调队列使用一个队列来实现。

单调队列就是确定了一个框后，从头开始，不断往右滑。通过这个窗口，我们就可以知道此窗口内的极值（max,min 之类的）。

注：队列里面存的是元素下标，而不是元素本身。

实现：

每次遍历到一个新元素时，从尾段（t）开始把比它弱的都干掉（t--），然后再把自己存进去（q[\ ++t\ ]=p）。如果头端超出了窗口，就剪掉（h++）。

这样一来，队列的头端就一定是当前这个窗口的极值（q[\ h\ ]）。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int n,l,r,a[N],f[N],h=1,t=1,q[N],ans=-0x3f;
signed main(){
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++)cin>>a[i];
    memset(f,-0x4f,sizeof(f));
    f[0]=0;
    for(int i=l;i<=n;i++){
        while(h<=t&&f[i-l]>=f[q[t]])t--;
        q[++t]=i-l;
        while(q[h]+r<i)h++;
        f[i]=a[i]+f[q[h]];
        if(i>n-r)ans=max(ans,f[i]);
    }
    cout<<ans<<"\n";
    return 0;
}