正式训练题面

规则来源

• 赛项说明页码：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)。
• 最大值和最早编号维护。