Luogu P1886 滑动窗口 /【模板】单调队列

题目描述

https://www.luogu.com.cn/problem/P1886

solution

#include <iostream>
#include <cstdio>
#include <cctype>
#define maxn 1000010
#define gc getchar
using namespace std;

int read() {
    int x = 0; bool f = 0; char c = gc(); 
    while (!isdigit(c)) { if (c == '-') f = 1; c = gc(); }
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return f ? -x : x;
}

int n, k, a[maxn];

struct node {
    int p, v; 
} Q[maxn]; int h, t; 

int main() { 
    n = read(); k = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    h = 1; t = 0; 
    for (int i = 1; i <= n; ++i) {
        while (h <= t && Q[h].p + k <= i) ++h;
        while (h <= t && a[i] <= Q[t].v) --t;
        Q[++t].p = i; Q[t].v = a[i];
        if (i >= k) printf("%d ", Q[h].v);
    }
    h = 1; t = 0; putchar('\n');
    for (int i = 1; i <= n; ++i) {
        while (h <= t && Q[h].p + k <= i) ++h;
        while (h <= t && a[i] >= Q[t].v) --t;
        Q[++t].p = i; Q[t].v = a[i];
        if (i >= k) printf("%d ", Q[h].v);
    }
    return 0;
}