PRE505 校园矩形热力

难度梯度：T3+｜训练重点：二维前缀和

题目描述

给定 N×M 的整数热力图，处理 Q 次矩形查询。每次输入 (r1,c1,r2,c2)，表示左上角与右下角，求闭区间矩形内元素总和。

矩形含边界上的所有单元格。允许负数；每次查询互不影响原图。

输入格式

第一行 N M Q；随后 N 行各 M 个整数；随后 Q 行每行 r1 c1 r2 c2。

输出格式

每次查询输出一行整数。

样例输入

3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3

样例输出

12
28

样例说明

两个矩形分别求和为 1+2+4+5 与 5+6+8+9。

数据范围

1≤N,M≤1000；N×M≤10^6；1≤Q≤2×10^5；-10^9≤格子值≤10^9。

子任务

30 分：N,M≤50,Q≤100；70 分：无附加限制。