题解 P1886 【滑动窗口】

· · 题解

这道题是单调队列的模版题，一看数据1000000，就知道暴力DP是九死一生

下面讲讲什么是单调队列，知道的dalao请跳过

单调队列分为单调递增和单调递减两种，我们只需要维护这个单调队列，怎么维护？

  1. 以递增序列为例

插入：如果将要插入的元素x>队尾元素，x直接入队，若x<=队尾元素，则弹出队尾元素，直到x>队尾元素

访问：如果要想得到小元素，直接访问队首元素即可

而这道题，我们只需要维护一个单调递增队列和一个单调递减队列，同时判断队首元素是否合法（即其是否在区间内），再用一个ans数组来记录答案，特别注意最左端是从k开始，因为区间不能越界

接下来上代码，建议不要照这些，先想一下，实在想不出来再看

好吧，太啰嗦了

#include<iostream>
#include<cstdio>
using namespace std;
int q1[1000005],q2[1000005],l1,l2,r1,r2,n,k,a[1000005],ans1[1000005],ans2[1000005];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        while(q1[l1]<i-k+1&&l1<=r1)l1++;
        while(a[q1[r1]]>a[i]&&r1>=l1)r1--;
        q1[++r1]=i;
        ans1[i]=a[q1[l1]];
        while(q2[l2]<i-k+1&&r2>=l2) l2++;
        while(a[q2[r2]]<a[i]&&r2>=l2) r2--;
        q2[++r2]=i;
        ans2[i]=a[q2[l2]];
    }
    for(int i=k;i<=n;i++) printf("%d ",ans1[i]);
    printf("\n");
    for(int i=k;i<=n;i++) printf("%d ",ans2[i]);
}