洛谷 P5788 【模板】单调栈

// P5788 的参照物：照定义两重循环 —— O(n²)
//
// 题面给的 60% 那一档是 n ≤ 5×10³ ⇒ 这一版**稳拿 60 分**（2.5×10⁷ 次比较）。
// 而 100% 那档 n = 3×10⁶，它要 4.5×10¹² 次 —— 差六个数量级。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        int ans = 0;
        for (int j = i + 1; j <= n; j++)
            if (a[j] > a[i]) { ans = j; break; }
        cout << ans << (i == n ? '\n' : ' ');
    }
    return 0;
}

// P5788【模板】单调栈 —— ★ 这一版就能 AC
//
//   f(i) = 第 i 个元素之后**第一个大于 a[i]** 的下标，不存在为 0。
//
// ★ 关键一步（本章第 5 步）：倒着扫，栈里存**下标**，栈里的值自栈顶向下递增。
//   要给 i 找答案，就把栈顶那些「不比 a[i] 大」的全弹掉 —— 它们永远轮不到了：
//   任何比 i 更靠左的位置要往右看，都会先撞上 a[i]。
//
// ⚠ 这道题真正的关卡不是算法，是 I/O：n = 3×10⁶ ⇒ 输入约 32 MB、输出约 20 MB，
//   时限 1 秒。所以这一版读和写都是手写的（见本页第 ⑤ 步那张表）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 3000005;
static int a[N], f[N], stk[N];

/* ⚠ 缓冲区是「读完就续」的窗口，不是「一口气全塞进来」——
   第 12 章 P1010 那一跤：拿一个固定大小的大数组去装整份输入，
   一旦估小了就**一声不吭地少读一截**，而所有版本一起错、对拍全绿。 */
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;
}

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) { pc('0'); return; }
    char t[12];
    int c = 0;
    while (x) { t[c++] = char('0' + x % 10); x /= 10; }
    while (c) pc(t[--c]);
}

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

    int top = 0;
    for (int i = n; i >= 1; i--) {
        while (top && a[stk[top]] <= a[i]) top--;   // ★ 相等也要弹：题面要的是「大于」
        f[i] = top ? stk[top] : 0;
        stk[++top] = i;
    }

    for (int i = 1; i <= n; i++) { wr(f[i]); pc(i == n ? '\n' : ' '); }
    flushOut();
    return 0;
}

// P5788 · 错法 ①：弹栈条件写成**严格小于** —— 相等的不弹
//
//   while (top && a[stk[top]] <  a[i]) top--;     ← 错
//   while (top && a[stk[top]] <= a[i]) top--;     ← 对
//
// ⇒ 它求的是「第一个**大于等于** a[i] 的下标」，而题面要的是「第一个**大于**」。
// ⚠ 触发条件只有一句话：**存在 j > i，a[j] == a[i]，而且 j 是第一个 ≥ a[i] 的位置**。
//    ⇒ 序列里没有重复元素时，它和正解**逐字节相同**（本页第 ③ 步量了这条曲线）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 3000005;
static int a[N], f[N], stk[N];

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

    int top = 0;
    for (int i = n; i >= 1; i--) {
        while (top && a[stk[top]] < a[i]) top--;   // ✗ 少了那个等号
        f[i] = top ? stk[top] : 0;
        stk[++top] = i;
    }

    for (int i = 1; i <= n; i++) cout << f[i] << (i == n ? '\n' : ' ');
    return 0;
}

// P5788 · 错法 ②：把 while 改成 if —— 一次只弹一个
//
// ⚠ 这个错法的来处很具体：本章第 6 步那句「for 里套 while，为什么还是 O(n)」
//    正是给它准备的。看不懂均摊分析的人，很容易「为了保住 O(n)」把 while 降成 if。
//
// ⇒ 它一次只丢掉一个候选，于是栈里会留下比 a[i] 矮的元素，f[i] 指到它头上就错了。
//    触发条件：某一步**需要连着弹两个或更多**。
#include <bits/stdc++.h>
using namespace std;

static const int N = 3000005;
static int a[N], f[N], stk[N];

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

    int top = 0;
    for (int i = n; i >= 1; i--) {
        if (top && a[stk[top]] <= a[i]) top--;     // ✗ while 降成了 if
        f[i] = top ? stk[top] : 0;
        stk[++top] = i;
    }

    for (int i = 1; i <= n; i++) cout << f[i] << (i == n ? '\n' : ' ');
    return 0;
}

// P5788 · 错法 ③：方向背成了死的 —— 求的是「**前面**第一个更大的」
//
// 单调栈的模板在不同的书上朝向不同（有的从左往右、有的从右往左），
// 背了模板却没看题面那句「第 i 个元素**之后**」，就会写成这一版。
//
// ⚠ 它算的量是能说清楚的：g(i) = 第 i 个元素**之前**最近的、大于 a[i] 的下标。
//    ⇒ 严格**递增**的序列上它恒输出 0，而正解恒输出 i+1（除了最后一个）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 3000005;
static int a[N], f[N], stk[N];

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

    int top = 0;
    for (int i = 1; i <= n; i++) {              // ✗ 扫描方向反了
        while (top && a[stk[top]] <= a[i]) top--;
        f[i] = top ? stk[top] : 0;
        stk[++top] = i;
    }

    for (int i = 1; i <= n; i++) cout << f[i] << (i == n ? '\n' : ' ');
    return 0;
}