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

// P1886【模板】单调队列 / 滑动窗口 —— ★ 这一版就能 AC
//
// 两问用同一套骨架，只把比较符号反过来：
//   最小值：队尾弹掉「不比 a[i] 小」的 ⇒ 队列里的值从队头到队尾递增，队头就是最小
//   最大值：队尾弹掉「不比 a[i] 大」的 ⇒ 队头就是最大
//
// ★ 队列里存的是**下标**，不是值 —— 因为判「有没有滑出窗口」要拿下标算（本章第 9 步）。
//
// ⚠ 题面写着 aᵢ ∈ [−2³¹, 2³¹) —— 那正好是 int 的**全部**范围，一点余量都没有。
//   ⇒ ① 存得下，用 int 就够；② 但**任何自己造的哨兵值都是错的**（本页第 ③ 步）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1000006;
static int a[N], q[N];

static char ibuf[1 << 16];
static int ipos, ilen;
static inline char gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return 0; }
    return ibuf[ipos++];
}
static inline int rd() {
    char c = gc();
    while (c && c != '-' && (c < '0' || c > '9')) c = gc();
    bool neg = false;
    if (c == '-') { neg = true; c = gc(); }          // ⚠ 这一行不能少，见本页第 ⑤ 步
    long long x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return (int)(neg ? -x : x);                      // ★ 用 long long 中转：−2³¹ 的绝对值放不进 int
}

static char obuf[1 << 16];
static int opos;
static inline void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
static inline void pc(char c) { if (opos == (int)sizeof(obuf)) flushOut(); obuf[opos++] = c; }
static inline void wr(int x) {
    if (x < 0) { pc('-'); }
    unsigned v = x < 0 ? (unsigned)0 - (unsigned)x : (unsigned)x;   // ★ 同理，别写 -x
    char t[12];
    int c = 0;
    if (!v) t[c++] = '0';
    while (v) { t[c++] = char('0' + v % 10); v /= 10; }
    while (c) pc(t[--c]);
}

int main() {
    int n = rd(), k = rd();
    for (int i = 1; i <= n; i++) a[i] = rd();

    for (int pass = 0; pass < 2; pass++) {
        int head = 1, tail = 0;
        for (int i = 1; i <= n; i++) {
            /* 队尾：把「轮不到了」的弹掉 —— 它比 a[i] 差，还比 a[i] 先出窗 */
            while (head <= tail && (pass == 0 ? a[q[tail]] >= a[i] : a[q[tail]] <= a[i])) tail--;
            q[++tail] = i;
            /* 队头：滑出窗口的丢掉 —— ★ 判据是下标，不是值 */
            if (q[head] <= i - k) head++;
            if (i >= k) { wr(a[q[head]]); pc(i == n ? '\n' : ' '); }
        }
    }
    flushOut();
    return 0;
}

// P1886 · 错法 ①：⚠⚠ **参照物自己错了** —— 暴力里用 0x3f3f3f3f 当哨兵
//
//   int best = 0x3f3f3f3f;  for (...) best = min(best, a[j]);
//
// 这是写暴力时最顺手的一行，前面三十几章也一直这么写。
// ⚠ 可这道题的 aᵢ 能取到 int 的**每一个值** —— 只要窗口里的数全都大于
//   0x3f3f3f3f = 1 061 109 567，它就会把这个哨兵当成最小值打出来。
// ⇒ 本页第 ③ 步：**「INF 该写多大」这道算术题，在这道题上无解**。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int pass = 0; pass < 2; pass++) {
        for (int i = k; i <= n; i++) {
            int best = (pass == 0) ? 0x3f3f3f3f : -0x3f3f3f3f;   // ✗ 自己造的哨兵
            for (int j = i - k + 1; j <= i; j++)
                best = (pass == 0) ? min(best, a[j]) : max(best, a[j]);
            cout << best << (i == n ? '\n' : ' ');
        }
    }
    return 0;
}

// P1886 · 错法 ③：判「有没有滑出窗口」用**值**，不用**下标**
//
//   队列里存的是下标，可有人顺手存了值，于是出窗只能靠「队头等于刚滑走的那个数」来判：
//       if (val[head] == a[i - k]) head++;
//
// ⚠ 它在「窗口里没有重复元素」时看着是对的 —— 而一旦窗口里有两个相等的数，
//   刚滑走的那个和留在窗口里的那个长得一模一样，它就会**把还在窗口里的那个弹掉**。
// ★ 本章第 9 步专门强调过：**队列里比的是值，窗口边界是拿下标判的** —— 两件事。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1000006;
static int a[N], val[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int pass = 0; pass < 2; pass++) {
        int head = 1, tail = 0;
        string out;
        for (int i = 1; i <= n; i++) {
            while (head <= tail && (pass == 0 ? val[tail] >= a[i] : val[tail] <= a[i])) tail--;
            val[++tail] = a[i];
            if (i > k && head <= tail && val[head] == a[i - k]) head++;   // ✗ 拿值判出窗
            if (i >= k) { out += to_string(val[head]); out += (i == n ? '\n' : ' '); }
        }
        cout << out;
    }
    return 0;
}

// P1886 · 错法 ④：手写快读**忘了负号**
//
// 前面三十几章的题，aᵢ 清一色是正数，快读也就一直这么写：
//     while (c < '0' || c > '9') c = gc();      // 跳过所有非数字 —— 连负号一起跳了
// ⇒ 这道题的 aᵢ 可以是负的，`-3` 被读成 `3`，**一声不吭**。
//
// ⚠⚠ 而顺手写的生成器**只造正数** —— 于是这个 bug 在默认那一档是**精确的 0**
//    （本页第 ⑤ 步）。算法一个字没错，输入读错了。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1000006;
static int a[N], q[N];

static char ibuf[1 << 16];
static int ipos, ilen;
static inline char gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return 0; }
    return ibuf[ipos++];
}
static inline int rd() {
    char c = gc();
    while (c && (c < '0' || c > '9')) c = gc();       // ✗ 负号在这里被吃掉了
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

int main() {
    int n = rd(), k = rd();
    for (int i = 1; i <= n; i++) a[i] = rd();

    for (int pass = 0; pass < 2; pass++) {
        int head = 1, tail = 0;
        string out;
        for (int i = 1; i <= n; i++) {
            while (head <= tail && (pass == 0 ? a[q[tail]] >= a[i] : a[q[tail]] <= a[i])) tail--;
            q[++tail] = i;
            if (q[head] <= i - k) head++;
            if (i >= k) { out += to_string(a[q[head]]); out += (i == n ? '\n' : ' '); }
        }
        fputs(out.c_str(), stdout);
    }
    return 0;
}

// P1886 · 错法 ②：窗口还没满就开始输出（差一）
//
//   if (i >= k) 写成 if (i >= 1) —— 于是前 k−1 个「窗口」只有一部分元素也被打了出来。
// ⇒ 输出会多出 k−1 个数，两行都多。
// ★ 这是本章第 10 步那句「边界比模板本身更容易写错」的第一种形态。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1000006;
static int a[N], q[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int pass = 0; pass < 2; pass++) {
        int head = 1, tail = 0;
        string out;
        for (int i = 1; i <= n; i++) {
            while (head <= tail && (pass == 0 ? a[q[tail]] >= a[i] : a[q[tail]] <= a[i])) tail--;
            q[++tail] = i;
            if (q[head] <= i - k) head++;
            out += to_string(a[q[head]]);              // ✗ 少了 if (i >= k)
            out += (i == n ? '\n' : ' ');
        }
        cout << out;
    }
    return 0;
}