滑动窗口 3.30

单调队列模板题

每次先把已经超过范围的扔掉。

然后把范围内不可能成为最优解的扔掉。

然后入队。

很久以前写的代码：

#include<iostream>
#include<cstdio>

using namespace std;
#define maxn 10000007
int x,q[maxn],a[maxn],n,m,f,r;

inline void Init()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}
inline void Work()
{
    if(m==1)
    {
        for(register int i=1;i<=n;i++)
            printf("%d ",a[i]);
        printf("\n");
        for(register int i=1;i<=n;i++)
            printf("%d ",a[i]);
        printf("\n");
        return;
    }
    q[f=++r]=1;
    for(register int i=2;i<m;i++)
    {
        x=a[i];
        while(a[q[r]]>=x&&r>=f)
            r--;
        q[++r]=i;
    }
    for(register int i=1;i+m-1<=n;i++)
    {
        while(q[f]<i)
            f++;
        x=a[i+m-1];
        while(a[q[r]]>=x&&r>=f)
            r--;
        q[++r]=i+m-1;
        printf("%d ",a[q[f]]);
    }
    printf("\n");
    q[f=r=1]=1;
    for(register int i=2;i<m;i++)
    {
        x=a[i];
        while(a[q[r]]<=x&&r>=f)
            r--;
        q[++r]=i;
    }
    for(register int i=1;i+m-1<=n;i++)
    {
        while(q[f]<i)
            f++;
        x=a[i+m-1];
        while(a[q[r]]<=x&&r>=f)
            r--;
        q[++r]=i+m-1;
        printf("%d ",a[q[f]]);
    }
    printf("\n");
}
int main()
{
    Init();
    Work();
    return 0;
}