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

• 完整解题档案：complete-solution-dossier.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;
}