洛谷 P2866 [USACO06NOV] Bad Hair Day S

// P2866 [USACO06NOV] Bad Hair Day —— ★ 这一版就能 AC
//
// ★★★ 关键的一步是**换一个主语**：题面问「第 i 头能看到几头」，
//   而单调栈一句话能数的是「第 j 头**被几头看到**」——
//   两个和必然相等（数的是同一批「可见的有序对 (i, j)」，只是先按 i 分组还是按 j 分组）。
//
//   从左往右扫，栈里存**还没被挡住的**牛（身高自栈底向上递减）。
//   新来一头 i：把「不比它高」的全弹掉（那些牛被 i 挡死了）；
//   ⇒ **剩在栈里的每一头都看得见 i** ⇒ ans += 栈的大小。
//
// ⚠ 这个「一句话」只对「被几头看到」成立 —— 换成「我能看到几头」就必须去找
//   「右边第一个不比我矮的位置」再相减（见 p2866Direct.cpp），
//   而**照抄同一句话、只把方向反过来**就是 p2866Rev.cpp 那个错法（本页第 ② 步）。
//
// ⚠ 答案要开 long long：顶格 n = 8×10⁴ 全严格递减 ⇒ n(n−1)/2 ≈ 3.2×10⁹（本页第 ③ 步）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 80005;
static int h[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 >> h[i];

    long long ans = 0;
    int top = 0;
    for (int i = 1; i <= n; i++) {
        while (top && h[stk[top]] <= h[i]) top--;    // 比我矮或一样高的，看不到我后面
        ans += top;                                  // 栈里剩的都比我高 ⇒ 它们都看得到我
        stk[++top] = i;
    }
    cout << ans << '\n';
    return 0;
}

// P2866 · 错法 ①：把正解那句话原封不动地**反着扫一遍**
//
//   正解（p2866.cpp）：从左往右，弹掉不比我高的，ans += 栈的大小
//   这一版        ：从右往左，同样一行不改
//
// ⚠⚠ 这是写这一页时**当场踩的坑** —— 它看着完全对称，其实不是：
//   「ans += 栈的大小」数的是「**被**几头看到」，而这个量本身是有方向的。
// ★ 说清楚它算了什么：**它给出的是把整排牛前后颠倒之后的正确答案**
//   ⇒ 在**回文**的身高序列上它恒等于正解（本页第 ② 步，那一档是能证的精确 0）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 80005;
static int h[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 >> h[i];

    long long ans = 0;
    int top = 0;
    for (int i = n; i >= 1; i--) {
        while (top && h[stk[top]] <= h[i]) top--;     // ★ 等高也要弹：题面要的是严格大于
        ans += top;                                   // 弹完之后栈里剩几个，就能看到几头
        stk[++top] = i;
    }
    cout << ans << '\n';
    return 0;
}

// P2866 · 另一条正确的路：直接数「第 i 头能看到几头」
//
// ★ 它和 p2866.cpp 的主语相反，公式也完全不同：
//     Cᵢ = （右边第一个**不比我矮**的下标 j）− i − 1        （不存在就当 j = n+1）
//   单调栈从右往左扫，弹掉严格矮于我的，栈顶就是那个 j。
//
// ⇒ 两版一行代码都不共享，拿它当参照物顶格也跑得动
//   （[P1803](/sol/p1803/) 那条：参照物不必是暴力）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 80005;
static int h[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 >> h[i];

    long long ans = 0;
    int top = 0;
    for (int i = n; i >= 1; i--) {
        while (top && h[stk[top]] < h[i]) top--;     // 弹掉严格比我矮的
        int j = top ? stk[top] : n + 1;              // 右边第一个不比我矮的
        ans += j - i - 1;
        stk[++top] = i;
    }
    cout << ans << '\n';
    return 0;
}

// P2866 · 错法 ①：答案用 int
//
// ⚠ 上界是 n(n−1)/2（全体严格递减时取到）：顶格 n = 8×10⁴ ⇒ 3 199 960 000，
//   而 int 只到 2 147 483 647 ⇒ **1.49 倍**，刚好越过去。
// ★ 那条分界线是 n = 65537（本页第 ③ 步：它和第 11 章 P1908 那条**一字不差**）。
// ⚠ 而小数据对拍**结构上**抓不到它 —— 只能算。
// ★ 演示用 unsigned 累加、最后按 int 打出来 —— 这样绕回的那个数是**可复现**的
//   （第 45 章那条：别拿 UB 派生的数字写断言）。
// ⚠ 注意：顶格答案 3 199 960 000 其实还塞得进 **unsigned**（上限 42.9 亿）——
//   真正装不下的是 **有符号** int，所以这一版的错误发生在**打出来那一刻**。
#include <bits/stdc++.h>
using namespace std;

static const int N = 80005;
static int h[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 >> h[i];

    unsigned ans = 0;                                 // ✗ 32 位
    int top = 0;
    for (int i = 1; i <= n; i++) {
        while (top && h[stk[top]] <= h[i]) top--;
        ans += (unsigned)top;
        stk[++top] = i;
    }
    cout << (int)ans << '\n';        // ✗ 有符号 int 装不下
    return 0;
}

// P2866 · 错法 ②：弹栈条件少了等号 —— 以为「一样高也看得过去」
//
//   while (top && h[stk[top]] <  h[i]) top--;    ← 错（等高的留在栈里，被当成能看到的）
//   while (top && h[stk[top]] <= h[i]) top--;    ← 对
//
// ⚠ 题面写得很死：`hᵢ > hᵢ₊₁, hᵢ > hᵢ₊₂, …` —— **严格大于**，等高就挡住了。
// ⇒ 触发条件只有一句：**输入里得有两头一样高的牛**（本页第 ④ 步量了这条曲线）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 80005;
static int h[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 >> h[i];

    long long ans = 0;
    int top = 0;
    for (int i = 1; i <= n; i++) {
        while (top && h[stk[top]] < h[i]) top--;      // ✗ 少了那个等号
        ans += top;
        stk[++top] = i;
    }
    cout << ans << '\n';
    return 0;
}