【luogu1886】 滑动窗口 [单调队列]

P1886 滑动窗口 

学的时候学得一愣一愣的 现在再打也是一愣一愣的

emmmm其实很简单 就是不想去仔细推 很重要就对了！ 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
const int N=1000000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int n,m,h,t,a[N],q[N],id[N];
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)>(y)?(y):(x)

void ueMin(){
    h=1,t=0;
    for(int i=1;i<=n;++i){
        while(h<=t&&id[h]+m<=i) ++h;
        while(h<=t&&a[i]<a[id[t]]) --t;
        id[++t]=i;
        if(i>=m) printf("%d ",a[id[h]]);
    }
    puts("");
}

void ueMax(){
    h=1,t=0;
    for(int i=1;i<=n;++i){
        while(h<=t&&id[h]+m<=i) ++h;
        while(h<=t&&a[i]>a[id[t]]) --t;
        id[++t]=i;
        if(i>=m) printf("%d ",a[id[h]]);
    }
}

int main(){
//    freopen("in.txt","r",stdin);
    rd(n),rd(m);
    for(int i=1;i<=n;++i) rd(a[i]);
    ueMin();
    memset(id,0,sizeof(id));
    ueMax();
    return 0;
}