在 NOI 竞赛中，构造“接雨水”这一类问题的测试数据时，需要特别关注地形的起伏特征。如果数据纯随机，往往会产生大量细小的水坑；而真正考验算法（尤其是单调栈边界处理）的是那些深度极大、跨度极广的“大峡谷”。

以下是为你准备的自动化数据生成器。它采用 C++14 标准，集成了标程逻辑，能够一键生成 10 组涵盖各种极端情况的测试点。

【数据生成器 C++ 代码】

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>

using namespace std;

typedef long long ll;

// --- 标准答案算法 (O(n) 单调栈迭代版) ---
// 采用横向填坑法，计算每一层凹槽的面积
ll solve(int n, const vector<int>& h) {
    if (n <= 2) return 0;
    
    // 使用静态数组模拟栈，避免频繁分配内存，防止大 $N$ 时爆栈
    static int stk[100005]; 
    int top = 0;
    ll total_water = 0;

    for (int i = 0; i < n; i++) {
        // 当当前柱子高度大于栈顶高度，说明找到了右边界，可能形成凹槽
        while (top > 0 && h[i] > h[stk[top]]) {
            int mid = stk[top--]; // 凹槽底部
            if (top == 0) break;   // 没有左边界，接不住水
            
            int left = stk[top];   // 左边界
            int right = i;         // 右边界
            
            // 计算当前层的水位高度：min(左墙, 右墙) - 坑底
            int height = min(h[left], h[right]) - h[mid];
            // 计算当前层的宽度：右墙下标 - 左墙下标 - 1
            int width = right - left - 1;
            
            total_water += (ll)height * width;
        }
        stk[++top] = i;
    }
    return total_water;
}

// --- 数据写入辅助函数 ---
void writeTestCase(int id, int n, const vector<int>& h) {
    // 写入 .in 文件
    string in_name = to_string(id) + ".in";
    ofstream fin(in_name);
    fin << n << "\n";
    for (int i = 0; i < n; i++) {
        fin << h[i] << (i == n - 1 ? "" : " ");
    }
    fin << endl;
    fin.close();

    // 写入 .out 文件
    string out_name = to_string(id) + ".out";
    ofstream fout(out_name);
    fout << solve(n, h) << endl;
    fout.close();
}

int main() {
    // 随机数种子使用固定值以保证数据可复现，也可改为 time(0)
    mt19937 rng(20251223);
    auto getRand = [&](int l, int r) {
        return uniform_int_distribution<int>(l, r)(rng);
    };

    const int MAXH = 100000;

    for (int t = 1; t <= 10; t++) {
        int n;
        vector<int> h;

        if (t == 1) { // 样例数据
            n = 12; h = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        } 
        else if (t == 2) { // 极小规模：$n=1$
            n = 1; h = {MAXH};
        }
        else if (t == 3) { // 阶梯状上升：$0, 1, 2, 3...$ (积水量应为 0)
            n = 1000;
            for (int i = 0; i < n; i++) h.push_back(i);
        }
        else if (t == 4) { // 阶梯状下降：$n, n-1... 0$ (积水量应为 0)
            n = 1000;
            for (int i = n; i >= 1; i--) h.push_back(i);
        }
        else if (t == 5) { // V 型山谷：巨大的储水池
            n = 50000;
            for (int i = n/2; i >= 1; i--) h.push_back(i);
            for (int i = 1; i <= n/2; i++) h.push_back(i);
        }
        else if (t == 6) { // 锯齿形：频繁的小坑
            n = 10000;
            for (int i = 0; i < n; i++) h.push_back(i % 2 == 0 ? 100 : 50);
        }
        else if (t == 7) { // 只有两头高，中间全是 0
            n = 100000;
            h.assign(n, 0);
            h[0] = MAXH; h[n-1] = MAXH;
        }
        else if (t == 8) { // 随机大规模 A
            n = 80000;
            for (int i = 0; i < n; i++) h.push_back(getRand(0, 500));
        }
        else if (t == 9) { // 随机大规模 B (包含极高柱子)
            n = 100000;
            for (int i = 0; i < n; i++) h.push_back(getRand(0, MAXH));
        }
        else { // 极端测试：平地
            n = 100000;
            h.assign(n, 555);
        }

        writeTestCase(t, n, h);
        cout << "Test Case " << t << " generated. n = " << n << endl;
    }

    return 0;
}

测试点覆盖策略说明：

1. 测试点 1 (Sample)：完全复现题面样例，确保基础逻辑通过。
2. 测试点 2 (Minimal)：$n=1$。测试程序在柱子极少时是否会崩溃或错误输出非零值。
3. 测试点 3 & 4 (Monotonic)：严格递增和严格递减。这种地形无法接雨水，测试程序是否能正确输出 0，并检测单调栈在只进不跳或只跳不进时的表现。
4. 测试点 5 (V-Shape)：这是一个深达 $25000$ 单位的大坑。由于跨度极大且深度均匀，可以测试 long long 溢出风险以及单调栈在长距离跨度下的正确性。
5. 测试点 6 (Sawtooth)：锯齿形状。测试单调栈频繁弹出、压入的性能。
6. 测试点 7 (Pool)：极限储水测试。两端为最高柱子，中间全部为 0。这是计算面积最大的情况，测试 total_water 的上限。
7. 测试点 8 (Low Random)：随机生成的低矮地形，模拟真实波动。
8. 测试点 9 (High Random)：$10^5$ 规模的随机高度地形。由于高度最高可达 $10^5$，这是对单调栈计算精度的终极考验。
9. 测试点 10 (Flat)：所有柱子高度一致。测试“等于”关系是否处理正确（即平地不积水）。

生成器技术细节建议：

• 内存管理：标程 solve 函数中使用了 static int stk[]。在生成 $10^5$ 规模数据时，静态数组分配在数据段，不会占用有限的系统栈空间（System Stack），有效防止生成过程中出现 Segment Fault。
• 非递归性：数据生成和标程均采用 for 循环迭代，不存在递归逻辑，确保了在大规模数据生成时的稳定性。
• 计算精度：积水量计算公式 ans += (ll)height * width 中，强制类型转换 (ll) 非常重要，防止中间结果在 int 范围内溢出。

你好，同学。用单调栈来解“接雨水”，实际上是在模拟一个“横向填坑”的过程。相比双指针的按列计算，单调栈的逻辑更具通用性（比如在寻找第一个比自己高的元素时顺便处理逻辑）。

以下是按照 NOIP 竞赛标准编写的 C++14 代码。

【标准题解代码】

#include <cstdio>
#include <algorithm>

using namespace std;

/**
 * 易错点 1：数据范围。
 * n = 10^5, h = 10^5。极端情况下（如一个巨大的 V 型山谷），
 * 总积水量会超过 2*10^9，因此 ans 必须使用 long long。
 */
typedef long long ll;

const int MAXN = 100005;
int h[MAXN];
int stk[MAXN]; // 手写栈：存储下标
int top = 0;   // 栈顶指针，0 表示栈空

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    for (int i = 0; i < n; i++) {
        scanf("%d", &h[i]);
    }

    ll ans = 0;

    for (int i = 0; i < n; i++) {
        /**
         * 维护单调递减栈：
         * 如果当前高度 h[i] 大于栈顶高度 h[stk[top]]，说明形成了一个“低洼”。
         */
        while (top > 0 && h[i] > h[stk[top]]) {
            // 1. 确定坑底高度
            int mid = stk[top--]; 
            
            // 2. 如果弹出坑底后栈空了，说明左边没有墙，接不住水
            if (top == 0) break;

            // 3. 确定左墙和右墙
            int left = stk[top];  // 左墙下标
            int right = i;        // 右墙下标（当前遍历到的柱子）

            /**
             * 关键点：横向计算水量
             * 高度 = min(左墙高, 右墙高) - 坑底高
             * 宽度 = 右墙下标 - 左墙下标 - 1
             */
            int height = min(h[left], h[right]) - h[mid];
            int width = right - left - 1;

            ans += (ll)height * width;
        }
        
        // 将当前下标压入栈中，继续寻找下一个可能的右墙
        stk[++top] = i;
    }

    printf("%lld\n", ans);

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度：$O(n)$

• 思考过程：
  • 我们使用了一个 for 循环遍历 $n$ 个元素。
  • 内部虽然有 while 循环，但请注意：每个下标 $i$ 最多只会进栈一次（stk[++top]），也最多只会出栈一次（stk[top--]）。
  • 结论：总的操作次数是 $2n$。对于 $10^5$ 的数据规模，单调栈法可以在 10ms-30ms 内完成计算，完全符合 1s 的时限要求。

2. 空间复杂度：$O(n)$

• 思考过程：
  • h[] 数组占用 $10^5 \times 4$ 字节 $\approx 400$ KB。
  • stk[] 数组占用 $10^5 \times 4$ 字节 $\approx 400$ KB。
  • 结论：总空间消耗极小（不到 1MB），相对于 256MB 的竞赛限制非常安全。

三、 时间复杂度优化建议

1. 手写栈 vs STL： 在 NOI 竞赛中，std::stack 底层默认使用 std::deque，频繁的内存分配会有一定的常数开销。使用数组模拟栈（如本代码所示）能获得更快的运行速度。

2. 避免重复访问内存： 在 while 循环中，h[stk[top]] 会被多次访问。虽然现代编译器会对其进行缓存优化，但在手动编写逻辑时，将常用的变量提取出来可以微量提升效率。

3. 快读 (Fast I/O)： 当 $n$ 达到 $10^6$ 级别时，scanf 会成为瓶颈。可以考虑使用 getchar() 实现的读入优化函数。

四、 读题关键词总结 (避坑指南)

• “接水/盛水”：寻找凹槽。凹槽需要三部分：左墙、坑底、右墙。
• “单调性”：当你发现一旦右侧出现一个高柱子，左侧的某些低洼处就“结算”了，这就是单调栈的典型应用场景。
• 宽度计算 $i - left - 1$：这是最容易写错的地方。记住，宽度是不包含左右墙本身的空隙。
• 高度差为 0 的处理：如果当前柱子和栈顶柱子一样高，height 会计算为 0，这在逻辑上是正确的（平地不积水），无需专门写 if 判断，合并处理即可。

教练寄语： 双指针法像是“剥洋葱”，从外向内一层层看每一列能接多少；而单调栈法更像是“填坑”，从下向上横向填满每一个凹槽。掌握了单调栈，你就能处理更复杂的直方图问题。加油！