在 NOI 竞赛中，一个优秀的测试数据包需要包含各种极端边界条件（Corner Cases）。对于单调栈题目，我们需要特别构造递增序列、递减序列以及大量重复元素的序列来测试程序的鲁棒性。

以下代码是一个集成了“数据生成”与“标准算法”的自动化脚本。运行该程序后，它会在当前目录下自动生成 1.in/1.out 到 10.in/10.out 共 10 组测试点。

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

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

using namespace std;

// --- 标准答案算法部分 (O(n) 单调栈) ---
void solve(int n, const vector<int>& T, vector<int>& ans) {
    ans.assign(n, 0);
    static int stk[100005]; // 使用静态数组模拟栈，避免重复分配内存
    int top = 0;
    for (int i = 0; i < n; ++i) {
        while (top > 0 && T[i] > T[stk[top]]) {
            int prev = stk[top--];
            ans[prev] = i - prev;
        }
        stk[++top] = i;
    }
}

// --- 数据生成辅助函数 ---
void writeInput(int caseIdx, int n, const vector<int>& T) {
    string fileName = to_string(caseIdx) + ".in";
    ofstream fout(fileName);
    fout << n << "\n";
    for (int i = 0; i < n; ++i) {
        fout << T[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();
}

void writeOutput(int caseIdx, int n, const vector<int>& ans) {
    string fileName = to_string(caseIdx) + ".out";
    ofstream fout(fileName);
    for (int i = 0; i < n; ++i) {
        fout << ans[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();
}

// --- 主生成逻辑 ---
int main() {
    // 使用随机数引擎 C++11/14 标准
    mt19937 rng(1337); 
    auto getRand = [&](int minV, int maxV) {
        return uniform_int_distribution<int>(minV, maxV)(rng);
    };

    for (int i = 1; i <= 10; ++i) {
        int n;
        vector<int> T;

        // --- 分点构造策略 ---
        if (i == 1) { // 样例数据
            n = 8;
            T = {73, 74, 75, 71, 69, 72, 76, 73};
        }
        else if (i == 2) { // 极小规模边界
            n = 1;
            T = {30};
        }
        else if (i == 3) { // 严格递增序列 (所有 ans 均为 1, 除了最后一个)
            n = 1000;
            for (int j = 0; j < n; ++j) T.push_back(30 + (j % 70));
        }
        else if (i == 4) { // 严格递减序列 (所有 ans 均为 0)
            n = 1000;
            for (int j = 0; j < n; ++j) T.push_back(100 - (j % 70));
        }
        else if (i == 5) { // 全部相同温度 (所有 ans 均为 0)
            n = 5000;
            T.assign(n, 50);
        }
        else if (i == 6) { // 锯齿形序列 (70, 30, 70, 30...)
            n = 10000;
            for (int j = 0; j < n; ++j) T.push_back(j % 2 == 0 ? 70 : 30);
        }
        else if (i >= 7 && i <= 9) { // 大规模随机数据
            n = 100000;
            for (int j = 0; j < n; ++j) T.push_back(getRand(30, 100));
        }
        else { // 极限挑战：只有最后一天是最高温 (测试单调栈最长驻留情况)
            n = 100000;
            for (int j = 0; j < n - 1; ++j) T.push_back(30);
            T.push_back(100);
        }

        // --- 执行标程并输出 ---
        vector<int> ans;
        solve(n, T, ans);
        writeInput(i, n, T);
        writeOutput(i, n, ans);
        
        cout << "Generated Test Case " << i << ": n = " << n << endl;
    }

    return 0;
}

测试点分布说明（OJ 构建参考）：

技术要点提示：

1. 非递归性： 本题的标准解法（单调栈）本质是迭代的（for + while），不存在递归调用，因此天然不存在爆栈风险。在生成器中，我们也使用了非递归的 solve 函数。

2. 生成效率： 对于 $N=10^5$ 的数据，生成 10 组的时间复杂度为 $O(10 \times N)$。在普通现代电脑上，运行此生成器脚本只需不到 1 秒即可完成所有 .in 和 .out 的写入。

3. 随机性保证： 使用了 mt19937 随机数引擎，它比传统的 rand() 拥有更长的周期和更好的分布特性，是 NOI 竞赛中生成高随机度数据的推荐做法。

4. 内存安全： 虽然 std::vector 很方便，但在 solve 函数中，我们使用了 static 修饰的数组或预分配空间的 vector。在处理 $10^6$ 以上更高级别数据时，应尽量避免在循环内反复申请和释放内存。

你好，同学。作为教练，我需要提醒你，NOIP/NOI 竞赛中，代码的稳健性（Robustness）与执行效率同样重要。

这道题是单调栈的教科书式应用。在实现时，我们通常会为了追求更高的效率，使用**手写栈（Array-based Stack）**来代替 std::stack，并使用较快的输入输出方式。

以下是符合 NOI 竞赛要求的标准代码示例。

【标准题解代码】

#include <cstdio>
#include <iostream>

using namespace std;

// 常量定义，10^5 的数据量，数组开略大一点防止越界
const int MAXN = 100005;

int t[MAXN];      // 存储每日气温
int ans[MAXN];    // 存储结果
int stk[MAXN];    // 手写栈：存储温度数组的下标
int top = 0;      // 栈顶指针，top=0 表示栈为空

int main() {
    int n;
    // 使用 scanf 提高读入效率，在 10^5 级别数据下比 cin 快
    if (scanf("%d", &n) != 1) return 0;

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

    // 单调栈核心逻辑
    for (int i = 0; i < n; i++) {
        /*
         * 易错点：这里必须是 while 而不是 if。
         * 因为当前这一天的温度可能同时高于栈顶好几天的温度。
         * 关键点：栈内存储的是下标，这样才能计算天数差距。
         */
        while (top > 0 && t[i] > t[stk[top]]) {
            // 如果当前温度比栈顶温度高，说明找到了栈顶元素“下一个更高温”
            int prev_index = stk[top]; 
            ans[prev_index] = i - prev_index; // 计算日期差
            top--; // 出栈
        }
        
        /*
         * 维护单调性：将当前下标压入栈中。
         * 此时栈内下标对应的温度从栈底到栈顶一定是单调不增的。
         */
        stk[++top] = i; 
    }

    // 题目要求：如果之后都没有更高气温，则为 0。
    // 由于全局数组 ans 初始化即为 0，所以不需要额外处理栈内剩余元素。

    // 输出结果，注意 NOI 格式要求空格隔开，末尾无多余空格或有换行均可
    for (int i = 0; i < n; i++) {
        printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
    }

    return 0;
}

二、 复杂度分析思考过程

在 NOI 考场上，写完代码后必须进行严格的复杂度确认。

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

• 分析：虽然代码中有一个 while 循环嵌套在 for 循环内部，但这并不意味着它是 $O(n^2)$。
• 思考过程：请看每一个元素。每个下标 $i$ 最多只会被执行一次入栈操作（stk[++top] = i），并且一旦出栈（top--），它就再也不会进入逻辑了。
• 结论：入栈总次数为 $n$，出栈总次数最多为 $n$。总的操作步数与 $n$ 成线性关系。

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

• 分析：我们开启了 t[], ans[], stk[] 三个长度为 $n$ 的数组。
• 思考过程：$3 \times 10^5$ 个 int 类型数据，每个 int 占 4 字节，总共约占用 $1.2 \times 10^6$ 字节 $\approx 1.14$ MB。
• 结论：这远远低于题目给出的 256MB 限制，空间非常充裕。

三、 时间复杂度优化建议

虽然 $O(n)$ 已经是理论最优解，但在实际竞赛中，若遇到更严苛的时间限制（例如 $10^6$ 数据量且限时 0.2s），可以考虑以下优化：

1. 快读（Fast I/O）： scanf 虽然比 cin 快，但在极端数据下，使用 getchar() 手写的 read() 函数效率更高。

   inline int read() {
       int x = 0, f = 1; char ch = getchar();
       while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
       while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
       return x * f;
   }
   

2. 避免频繁入栈出栈的对象创建： 在 C++14 中，使用 std::stack 会有一定的对象维护开销。如上文所示，使用原生数组模拟栈，直接操作指针 top，是竞赛中最极致的写法。

3. 倒序遍历优化： 其实这道题也可以从右往左遍历。从右往左遍历时，栈内维护的是“右侧可能比我高的候选者”。这种思考方式在处理“左侧第一个比我高”和“右侧第一个比我高”同时存在的问题时（如：最大矩形面积）更加统一。

四、 考场注意事项

• 初始化：如果这道题有多组测试数据，记得在每组数据开始前清空 top = 0。
• 边界：下标是从 0 开始还是从 1 开始？在计算 i - prev_index 时要统一标准。
• 数据量：本题温度最高 100，天数最高 $10^5$，结果不会溢出 int。如果天数是 $10^9$（虽然不可能），则需要考虑 long long。