红色据点方格图：纪念点热度区域统计

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：10
• 训练题主题：红色据点方格图：纪念点热度区域统计
• 所属赛道：红色文化赛道

题目背景

红色据点展区被抽象为一个热度方格图。每个方格记录某个展陈点的关注热度，讲解团队需要多次统计矩形区域热度总和，并迅速定位最热门的查询区域。

任务描述

• 读取热度方格矩阵并构建二维前缀和。
• 对每个矩形查询输出区域热度总和。
• 输出区域和最大的查询编号和对应区域和，若并列取最早编号。

输入格式

1. 第一行输入 n m q，表示矩阵行数、列数和查询数量。
2. 接下来 n 行每行输入 m 个非负整数，表示热度矩阵。
3. 接下来 q 行每行输入 r1 c1 r2 c2，表示一个查询矩形。

输出格式

1. 第一行输出 results= 后接所有查询结果，结果之间用空格分隔。
2. 第二行输出 best_query=编号 区域和。

数据范围与说明

• 1 <= n, m <= 300。
• 1 <= q <= 10^5。
• 0 <= a[i][j] <= 10000。
• 1 <= r1 <= r2 <= n，1 <= c1 <= c2 <= m。
• 区域和必须使用 64 位整数。

样例输入

3 4 3
1 2 3 4
0 1 0 2
5 1 2 1
1 1 2 2
2 2 3 4
1 3 3 4

样例输出

results=4 7 12
best_query=3 12

样例解释

• 第一个查询矩形和为 1 + 2 + 0 + 1 = 4。
• 第二个查询矩形和为 1 + 0 + 2 + 1 + 2 + 1 = 7。
• 第三个查询区域和最大，为 12，因此 best_query=3 12。

知识点清单

• 二维数组建模。
• 二维前缀和定义与构造。
• 容斥公式求子矩形和。
• 多次查询从 O(nm) 降到 O(1)。
• 最大值和最早编号维护。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n, m <= 300。
• 1 <= q <= 10^5。
• 0 <= a[i][j] <= 10000。
• 1 <= r1 <= r2 <= n，1 <= c1 <= c2 <= m。
• 区域和必须使用 64 位整数。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 二维前缀和 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 查询矩形恰好从第一行或第一列开始时，要正确处理前缀边界。
• 查询数量很大时不能逐格重新累加。
• 多个查询得到相同最大值时，必须保留最早查询编号。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：exact
• 主算法：二维前缀和

判题重点

• 重点校验公式、排序规则和格式化输出是否完全一致。
• 隐藏数据会覆盖边界值、重复值和最小规模输入。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 准备单格查询、整张矩阵查询和边界矩形查询。
• 准备大量查询数据，验证二维前缀和的性能优势。
• 准备多个最大值并列的查询序列，检查编号规则。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• cpp 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

3 4 3
1 2 3 4
0 1 0 2
5 1 2 1
1 1 2 2
2 2 3 4
1 3 3 4

样例输出：sample.out

results=4 7 12
best_query=3 12

题解、建模与最终解法

自动整理的解题流程

• 题目主题：红色据点方格图：纪念点热度区域统计
• 题目摘要：建立二维前缀和后快速回答多次矩形热度查询，并找出区域和最大的查询。
• 判题提示：该题以精确输出为主，最终程序需要重点保证公式、顺序和格式完全一致。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

解题思路

源文件：solution-rationale.md

1. 问题重述

建立二维前缀和后快速回答多次矩形热度查询，并找出区域和最大的查询。

2. 数据结构与建模

• 主算法：二维前缀和
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 读入矩阵时同步构建二维前缀和表。
2. 对每个查询用容斥公式在 O(1) 时间求出矩形和。
3. 顺序记录所有查询结果，并维护区域和最大的查询编号。
4. 按要求输出结果列表和最佳查询信息。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 查询矩形恰好从第一行或第一列开始时，要正确处理前缀边界。
• 查询数量很大时不能逐格重新累加。
• 多个查询得到相同最大值时，必须保留最早查询编号。

7. 知识点清单

• 二维数组建模。
• 二维前缀和定义与构造。
• 容斥公式求子矩形和。
• 多次查询从 O(nm) 降到 O(1)。
• 最大值和最早编号维护。

设计决策记录

源文件：decision-log.md

• 选择 二维前缀和 作为主算法，因为它能直接覆盖题目的核心约束。
• 二维静态矩阵多次查询时，前缀和是最稳定的主方案。
• 结果列表需要保留原始查询顺序，因此边算边存最直接。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备单格查询、整张矩阵查询和边界矩形查询。
• 准备大量查询数据，验证二维前缀和的性能优势。
• 准备多个最大值并列的查询序列，检查编号规则。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    rows = next(it)
    cols = next(it)
    queries = next(it)
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for row in range(1, rows + 1):
        row_sum = 0
        for col in range(1, cols + 1):
            value = next(it)
            row_sum += value
            prefix[row][col] = prefix[row - 1][col] + row_sum
    answers = []
    best_query = 1
    best_sum = -1
    for query_id in range(1, queries + 1):
        r1 = next(it)
        c1 = next(it)
        r2 = next(it)
        c2 = next(it)
        total = prefix[r2][c2] - prefix[r1 - 1][c2] - prefix[r2][c1 - 1] + prefix[r1 - 1][c1 - 1]
        answers.append(str(total))
        if total > best_sum:
            best_sum = total
            best_query = query_id
    return f"results={' '.join(answers)}\nbest_query={best_query} {best_sum}"


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

C++ 对照实现

源文件：main.cpp

• 实现状态：当前已有可执行实现

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int rows, cols, queries;
    if (!(cin >> rows >> cols >> queries)) {
        return 0;
    }
    vector<vector<long long>> prefix(rows + 1, vector<long long>(cols + 1, 0));
    for (int row = 1; row <= rows; ++row) {
        long long row_sum = 0;
        for (int col = 1; col <= cols; ++col) {
            long long value;
            cin >> value;
            row_sum += value;
            prefix[row][col] = prefix[row - 1][col] + row_sum;
        }
    }
    vector<long long> answers;
    int best_query = 1;
    long long best_sum = -1;
    for (int query_id = 1; query_id <= queries; ++query_id) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        long long total = prefix[r2][c2] - prefix[r1 - 1][c2] - prefix[r2][c1 - 1] + prefix[r1 - 1][c1 - 1];
        answers.push_back(total);
        if (total > best_sum) {
            best_sum = total;
            best_query = query_id;
        }
    }
    cout << "results=";
    for (size_t i = 0; i < answers.size(); ++i) {
        if (i) {
            cout << ' ';
        }
        cout << answers[i];
    }
    cout << "\n";
    cout << "best_query=" << best_query << ' ' << best_sum << "\n";
    return 0;
}

代码执行与运行结果

最新成功运行

PY 运行输出摘录

results=4 7 12
best_query=3 12

CPP 运行输出摘录

results=4 7 12
best_query=3 12

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s2-jh-05-checkpoint-grid/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s2-jh-05-checkpoint-grid/02-solution
• 运行证据：10-cases/s2-jh-05-checkpoint-grid/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md

• 完整解题档案：complete-solution-dossier.md
• 代码附录：appendix-code.md
• 运行附录：appendix-runs.md

题目概述

建立二维前缀和后快速回答多次矩形热度查询，并找出区域和最大的查询。

最终解法摘要

自动整理的解题流程

• 题目主题：红色据点方格图：纪念点热度区域统计
• 题目摘要：建立二维前缀和后快速回答多次矩形热度查询，并找出区域和最大的查询。
• 判题提示：该题以精确输出为主，最终程序需要重点保证公式、顺序和格式完全一致。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

代码执行摘要

交付说明

本报告为摘要版，详细题目、题干、题解、最终代码、运行结果和调试流程已经汇总到完整解题档案中。