241971 - 二维区域和检索(矩阵不可变)

题目描述

给定一个 m 行 n 列的整数矩阵 a,之后有 q 次查询。

每次查询给出四个整数 r_1、c_1、r_2、c_2,表示一个矩形区域的左上角坐标为 (r_1,c_1),右下角坐标为 (r_2,c_2)。请计算这个矩形区域内所有元素的和,包含矩形边界上的元素。

在所有查询过程中,矩阵中的元素不会被修改。

矩阵的行、列下标均从 1 开始。

输入

第一行输入三个整数 m、n 和 q,分别表示矩阵的行数、列数和查询次数。

接下来 m 行,每行输入 n 个整数,第 i 行第 j 列的整数为 a_{i,j}。

接下来 q 行,每行输入四个整数 r_1、c_1、r_2、c_2,表示一次区域求和查询。

保证:

  • 1 \le m,n \le 200;
  • 1 \le q \le 10^4;
  • -10^5 \le a_{i,j} \le 10^5;
  • 1 \le r_1 \le r_2 \le m;
  • 1 \le c_1 \le c_2 \le n。
输出

对于每次查询,输出一行整数,表示指定矩形区域的元素和。

样例

输入

5 5 3
3 0 1 4 2
5 6 3 2 1
1 2 0 1 5
4 1 0 1 7
1 0 3 0 5
3 2 5 4
2 2 3 3
2 3 3 5

输出

8
11
12

输入

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

输出

1
1
-5
-2
说明

样例解释 1

第一次查询的区域为第 3 行至第 5 行、第 2 列至第 4 列,区域元素和为 2+0+1+1+0+1+0+3+0=8。

第二次查询的区域为第 2 行至第 3 行、第 2 列至第 3 列,区域元素和为 6+3+2+0=11。

第三次查询的区域为第 2 行至第 3 行、第 3 列至第 5 列,区域元素和为 3+2+1+0+1+5=12。

样例解释 2

第 1 次查询整个矩阵,元素和为 1;第 2 次查询第一行第 2 列至第 3 列,元素和为 1;第 3 次只查询元素 a_{2,3},答案为 -5;第 4 次查询第二列的两个元素,答案为 -2。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 3
通过人数 3
金币数量 3 枚
难度 入门


上一题 下一题