这是一个完整的 C++ 数据生成器，用于生成“二维区域和检索”题目的测试数据。

它包含了一个标准的二维前缀和解法，用于生成正确的 .out 文件，并精心设计了 10 个测试点，覆盖了从样例、边界情况（如 $1 \times 1$ 矩阵、单行、单列）到最大规模压力测试的各种场景。

数据生成器代码 (generator.cpp)

您可以将以下代码保存为 generator.cpp，编译并运行。它将在当前目录下生成 1.in/1.out 到 10.in/10.out。

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

using namespace std;

typedef long long ll;

// ==========================================
// 1. 标准解法函数 (用于生成 .out 文件)
// ==========================================
vector<ll> solve(int n, int m, const vector<vector<int>>& matrix, const vector<vector<int>>& queries) {
    // 预处理二维前缀和
    // s[i][j] 表示 (1,1) 到 (i,j) 的矩形和
    vector<vector<ll>> s(n + 1, vector<ll>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // matrix 是 0-based 存储的，所以取值用 matrix[i-1][j-1]
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }

    vector<ll> results;
    for (const auto& q : queries) {
        int x1 = q[0], y1 = q[1], x2 = q[2], y2 = q[3];
        // 查询公式
        ll ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        results.push_back(ans);
    }
    return results;
}

// ==========================================
// 2. 随机数辅助工具
// ==========================================
mt19937 rng(time(nullptr));

// 生成 [min, max] 范围内的随机整数
int random_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

// ==========================================
// 3. 测试点生成逻辑
// ==========================================
void generate_test_case(int id) {
    int N, M, Q;
    int min_val, max_val;
    string desc;

    // 根据 id 设定测试点参数
    switch (id) {
        case 1: // 样例数据
            N = 3; M = 4; Q = 3;
            min_val = 0; max_val = 0; // 样例固定，此处范围无效
            desc = "Sample Case";
            break;
        case 2: // 极小数据 (1x1)
            N = 1; M = 1; Q = 5;
            min_val = -10; max_val = 10;
            desc = "Smallest 1x1 Matrix";
            break;
        case 3: // 全 0 矩阵
            N = 10; M = 10; Q = 10;
            min_val = 0; max_val = 0;
            desc = "All Zeros";
            break;
        case 4: // 全正数
            N = 50; M = 50; Q = 100;
            min_val = 1; max_val = 1000;
            desc = "All Positive";
            break;
        case 5: // 全负数
            N = 50; M = 50; Q = 100;
            min_val = -1000; max_val = -1;
            desc = "All Negative";
            break;
        case 6: // 单行矩阵 (1x1000) - 降维测试
            N = 1; M = 1000; Q = 1000;
            min_val = -100; max_val = 100;
            desc = "Row Vector (1xM)";
            break;
        case 7: // 单列矩阵 (1000x1) - 降维测试
            N = 1000; M = 1; Q = 1000;
            min_val = -100; max_val = 100;
            desc = "Column Vector (Nx1)";
            break;
        case 8: // 中等规模混合数据
            N = 100; M = 100; Q = 5000;
            min_val = -1000; max_val = 1000;
            desc = "Medium Random";
            break;
        case 9: // 大规模，大数值，少量查询
            N = 1000; M = 1000; Q = 100;
            min_val = -1000; max_val = 1000;
            desc = "Large Matrix, Few Queries";
            break;
        case 10: // 最大规模压力测试
            N = 1000; M = 1000; Q = 100000;
            min_val = -1000; max_val = 1000;
            desc = "Max Constraints Stress Test";
            break;
        default:
            N = 10; M = 10; Q = 10;
            min_val = 0; max_val = 10;
    }

    // --- 生成矩阵数据 ---
    vector<vector<int>> matrix(N, vector<int>(M));
    if (id == 1) {
        // 样例固定数据
        matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12}
        };
    } else {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                matrix[i][j] = random_int(min_val, max_val);
            }
        }
    }

    // --- 生成查询数据 ---
    vector<vector<int>> queries;
    if (id == 1) {
        // 样例固定查询
        queries = {
            {1, 1, 2, 2},
            {2, 2, 3, 3},
            {1, 1, 3, 4}
        };
    } else {
        for (int k = 0; k < Q; ++k) {
            // 随机生成左上角 (x1, y1) 和 右下角 (x2, y2)
            int r1 = random_int(1, N);
            int r2 = random_int(1, N);
            int c1 = random_int(1, M);
            int c2 = random_int(1, M);

            int x1 = min(r1, r2);
            int x2 = max(r1, r2);
            int y1 = min(c1, c2);
            int y2 = max(c1, c2);

            queries.push_back({x1, y1, x2, y2});
        }
    }

    // --- 写入 .in 文件 ---
    string in_filename = to_string(id) + ".in";
    ofstream fin(in_filename);
    fin << N << " " << M << " " << Q << "\n";
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            fin << matrix[i][j] << (j == M - 1 ? "" : " ");
        }
        fin << "\n";
    }
    for (const auto& q : queries) {
        fin << q[0] << " " << q[1] << " " << q[2] << " " << q[3] << "\n";
    }
    fin.close();

    // --- 计算答案并写入 .out 文件 ---
    vector<ll> answers = solve(N, M, matrix, queries);
    string out_filename = to_string(id) + ".out";
    ofstream fout(out_filename);
    for (const auto& ans : answers) {
        fout << ans << "\n";
    }
    fout.close();

    cout << "Generated Case " << id << ": " << desc << " (N=" << N << ", M=" << M << ", Q=" << Q << ")" << endl;
}

int main() {
    // 为了加快大规模数据的 I/O 速度
    ios::sync_with_stdio(false);
    
    for (int i = 1; i <= 10; ++i) {
        generate_test_case(i);
    }
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

测试点详细设计说明

1. Case 1 (Sample): 题目描述中给出的样例。这是最基础的正确性验证。
2. Case 2 (Smallest): $1 \times 1$ 矩阵。测试程序处理边界下标（尤其是 $x-1$ 这种操作）是否会越界。
3. Case 3 (All Zeros): 全 0 矩阵。验证前缀和是否正确处理 0 值，结果应全为 0。
4. Case 4 (All Positive): 全正数。测试基本的累加逻辑，无负数干扰。
5. Case 5 (All Negative): 全负数。测试带符号整数的加减法，以及结果为负数的情况。
6. Case 6 (Row Vector): $1 \times 1000$。将二维问题退化为一维数组，测试是否能正确处理 $N=1$ 的情况。
7. Case 7 (Col Vector): $1000 \times 1$。测试是否能正确处理 $M=1$ 的情况。
8. Case 8 (Medium Mixed): $100 \times 100$。常规随机数据，正负混合。
9. Case 9 (Large Matrix): $1000 \times 1000$。测试构建前缀和数组的效率（$O(NM)$）。
10. Case 10 (Stress Test): $N=1000, M=1000, Q=100,000$。最大数据范围压力测试，验证程序是否会在 $O(1)$ 时间内响应查询（如果用暴力法会超时）。同时测试 long long 是否能防止溢出。

如何使用

1. 保存：将代码保存为 generator.cpp。
2. 编译：g++ generator.cpp -o generator -O2
3. 运行：./generator (Linux/Mac) 或 generator.exe (Windows)。
4. 结果：当前文件夹下会生成 1.in, 1.out ... 10.in, 10.out。这些文件可以直接打包上传到 OJ 系统。

/**
 * 题目：二维区域和检索
 * 知识点：二维前缀和 (2D Prefix Sum)
 * 时间复杂度：预处理 O(N*M), 查询 O(1)
 * 空间复杂度：O(N*M)
 */

#include <iostream>
#include <vector>

using namespace std;

// 使用 long long 防止多次累加后溢出 int
typedef long long ll;

const int MAXN = 1005; // 稍微开大一点防止越界
ll s[MAXN][MAXN];      // 二维前缀和数组，全局定义自动初始化为 0

int main() {
    // 1. IO 优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;

    // 2. 读入矩阵并同时计算二维前缀和
    // 这里的 s[i][j] 最终将存储 (1,1) 到 (i,j) 的矩形和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int val;
            cin >> val;
            
            // 核心构造公式：
            // 当前前缀和 = 上方 + 左方 - 左上重叠 + 当前值
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + val;
        }
    }

    // 3. 处理查询
    for (int k = 0; k < q; ++k) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // 核心查询公式 (容斥原理)：
        // 目标区域 = 大矩形 - 上半部 - 左半部 + 左上角被多减的一次
        ll ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

        cout << ans << "\n";
    }

    return 0;
}