该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
给定一个 n 行 m 列的整数矩阵,请回答 q 次相互独立的询问。每次询问给出 r1,c1,r2,c2,要求计算「第 r1 行到第 r2 行、第 c1 列到第 c2 列」这个小矩形内所有元素的总和。
行范围和列范围都是闭区间:四条边界上的元素都要计入。也就是说,答案是
i=r1∑r2 j=c1∑c2ai,j,
其中 ai,j 表示第 i 行第 j 列的元素。
输入格式
第一行输入三个整数 n,m,q(1≤n,m≤100,1≤q≤1000),依次表示矩阵的行数、列数和询问次数。
接下来 n 行,每行 m 个整数。第 i 行的第 j 个整数是 ai,j(−109≤ai,j≤109)。
接下来 q 行,每行四个整数 r1,c1,r2,c2(1≤r1≤r2≤n,1≤c1≤c2≤m),表示一次询问。矩阵的行、列下标都从 1 开始。
输出格式
输出 q 行,第 k 行为一个整数,表示第 k 次询问的子矩阵元素和。
样例
3 4 7
1000000000 1000000000 1000000000 -1000000000
1000000000 -1000000000 1000000000 1000000000
-1000000000 1000000000 1000000000 1000000000
1 1 3 4
1 1 2 2
2 2 3 3
1 3 1 3
2 4 3 4
1 1 3 1
1 4 3 4
6000000000
2000000000
2000000000
1000000000
2000000000
1000000000
1000000000
样例解释:
- 第 1 次询问覆盖整个 3×4 矩阵,和为 6000000000,已经超过 32 位有符号整数的上界。
- 第 2 次询问覆盖 (1,1) 到 (2,2) 四个格子,即 109+109+109−109=2×109。
- 第 3 次询问覆盖 (2,2) 到 (3,3) 四个格子,同样得到 2×109。
- 第 4 次询问只覆盖一个格子 (1,3),答案为 109。
- 第 5 次询问覆盖 (2,4)、(3,4) 两个格子,109+109=2×109。
- 第 6 次询问只取第 1 列的三行,109+109−109=109;第 7 次询问只取第 4 列的三行,−109+109+109=109。
数据范围
- 1≤n,m≤100;
- 1≤q≤1000;
- −109≤ai,j≤109;
- 1≤r1≤r2≤n,1≤c1≤c2≤m,保证每次询问的矩形非空。
说明
- 每次询问都必须包含 r1,r2 两行和 c1,c2 两列的边界元素,不能把闭区间当成半开区间。
- 即使 r1=r2 或 c1=c2,询问依然合法:前者表示一行,后者表示一列,两者都成立时表示一个格子。
- 单个答案的绝对值最大可达 100×100×109=1013,超出 32 位整数范围,请用
long long 等 64 位整数保存累加结果。
- 在本题数据范围内,对每次询问直接枚举它覆盖的格子并累加即可通过(最坏 q⋅n⋅m≤107 次加法),不要求使用二维前缀和或二维差分。