模板题留名/x

这题就是一个单调队列模板题（真模板题，被各个大佬用于单调队列的讲解）

由于不想水题解，就在这里讲讲单调队列吧。。。

我们用此题来讲解。

假设我们现在在求窗口中的最小值，那么，如果满足存在两个位置:i,j在同一个窗口(i<j)，如果a[i]>=a[j]，那么，一定有答案不可能是a[i]。(当然，如果a[i]==a[j]，我们把答案看做a[j]而不是a[i]也是成立的)

为啥呢？

因为，我们发现，我们滑动“窗口”时，是逐个删除前面的数，也就是说，i一定会比j先被删除。

所以，i还在窗口时，j也肯定在窗口，而，又由于a[i]>=a[j],所以，答案最小值不会取到a[i]的（要取也是取的a[j]）

所以，如果窗口存在一个i满足，存在一个j>i,a[i]>=a[j]，那么，我们把这个i删除即可

那么，我们看看，如果我们把剩下的数按照下标由小到大排序的话，会是什么样子：

因为不存在i<j,a[i]>=a[j]的情况，所以，剩下的数一定满足:

i<j,a[i]<a[j],也就是说，我们当前窗口的答案就是剩下的点中，下标最小的点的值

那么，我们如果将窗口"滑动"会怎么样？

窗口滑动后，我们会删除一个数，同时添加一个数，我们先考虑删除一个数。

我们有如下讨论：

如果，删除的那个数在我们删除无用的数后的剩下的窗口中，那么，它一定是第一个数。

所以，我们判断下第一个是不是需要删除的那个数，然后判断是否把它删除即可。

然后，我们再来看看添加一个数，因为，我们添加的这个数一定比窗口里面的所有数的下标都大，所以，它一定会留在窗口里面，我们只需用这个数去判断下窗口剩下的数合不合法即可。

设窗口中剩下两个点i,j,这个点为k(i<j<k)

如果a[i]>=a[k],因为a[j]>=a[i],所以,如果i不合法，j肯定也不合法，所以我们可以从"窗口"的后面倒着判断每个点是否合法，然后删除即可。

因为我们注意到，我们的"窗口"需要删除第一个数和最后一个数，所以我们使用双端队列维护即可。

复杂度分析:由于判断O(1),每个点最多进入，删除,队列一次，而且，如果越过这个点遍历其他点的话，这个点一定会被删除，所以，复杂度是O(n)

Ps:由于本题有点特殊，判断第一个数是否删除的时候可以直接写if，不过大多数情况是直接写的while(因为可能与位置无关导致一开始窗口有多个"过期"的点)

本题代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int a[N],que[N],l=1,r;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    que[++r]=1;
    for(int i=2;i<=k;++i){
        while(l<=r&&a[que[r]]>=a[i]){
            --r;
        }
        que[++r]=i;
    }
    printf("%d ",a[que[l]]);
    for(int i=k+1;i<=n;++i){
        if(que[l]==i-k){
            ++l;
        }
        while(l<=r&&a[que[r]]>=a[i]){
            --r;
        }
        que[++r]=i;
        printf("%d ",a[que[l]]);
    }
    puts("");
    l=1,r=0;
    que[++r]=1;
    for(int i=2;i<=k;++i){
        while(l<=r&&a[que[r]]<=a[i]){
            --r;
        }
        que[++r]=i;
    }
    printf("%d ",a[que[l]]);
    for(int i=k+1;i<=n;++i){
        if(que[l]==i-k){
            ++l;
        }
        while(l<=r&&a[que[r]]<=a[i]){
            --r;
        }
        que[++r]=i;
        printf("%d ",a[que[l]]);
    }
    return 0;
}