#10161. 二维前缀和模板

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: xield

题目描述

给定一个 n*m 的矩阵,矩阵中的元素都是整数。 给定k个询问: a[i][j] 为左上角顶点, a[p][q] 为右下角顶点所组成的小矩阵中,所有元素的和为多少。

输入格式

第一行为三个整数 n , m , k

接下来为一个 n * m 的矩阵。

接下来的k行,每行有四个整数 i , j , p , q

输出格式

输出询问的矩形区域中,所有元素之和。

样例

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

8
27
5

数据范围与提示

对于所有的数据: 1≤n,m,k≤1000

对所有的数据: i<=p,j<=q

对矩阵中的任意一个元素、任意一个区域的元素和,均不会超过long long 的表示范围。