AK. 子矩阵求和

    传统题 1000ms 256MiB

子矩阵求和

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

给定一个 nn 行 mm 列的整数矩阵,请回答 qq 次相互独立的询问。每次询问给出 r1,c1,r2,c2r_1,c_1,r_2,c_2,要求计算「第 r1r_1 行到第 r2r_2 行、第 c1c_1 列到第 c2c_2 列」这个小矩形内所有元素的总和。

行范围和列范围都是闭区间:四条边界上的元素都要计入。也就是说,答案是

∑i=r1r2 ∑j=c1c2ai,j,\sum_{i=r_1}^{r_2}\ \sum_{j=c_1}^{c_2} a_{i,j},

其中 ai,ja_{i,j} 表示第 ii 行第 jj 列的元素。

输入格式

第一行输入三个整数 n,m,qn,m,q(1≤n,m≤1001\le n,m\le 100,1≤q≤10001\le q\le 1000),依次表示矩阵的行数、列数和询问次数。

接下来 nn 行,每行 mm 个整数。第 ii 行的第 jj 个整数是 ai,ja_{i,j}(−109≤ai,j≤109-10^9\le a_{i,j}\le 10^9)。

接下来 qq 行,每行四个整数 r1,c1,r2,c2r_1,c_1,r_2,c_2(1≤r1≤r2≤n1\le r_1\le r_2\le n,1≤c1≤c2≤m1\le c_1\le c_2\le m),表示一次询问。矩阵的行、列下标都从 11 开始。

输出格式

输出 qq 行,第 kk 行为一个整数,表示第 kk 次询问的子矩阵元素和。

样例

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

样例解释:

  • 第 11 次询问覆盖整个 3×43\times 4 矩阵,和为 60000000006000000000,已经超过 3232 位有符号整数的上界。
  • 第 22 次询问覆盖 (1,1)(1,1) 到 (2,2)(2,2) 四个格子,即 109+109+109−109=2×10910^9+10^9+10^9-10^9=2\times 10^9。
  • 第 33 次询问覆盖 (2,2)(2,2) 到 (3,3)(3,3) 四个格子,同样得到 2×1092\times 10^9。
  • 第 44 次询问只覆盖一个格子 (1,3)(1,3),答案为 10910^9。
  • 第 55 次询问覆盖 (2,4)(2,4)、(3,4)(3,4) 两个格子,109+109=2×10910^9+10^9=2\times 10^9。
  • 第 66 次询问只取第 11 列的三行,109+109−109=10910^9+10^9-10^9=10^9;第 77 次询问只取第 44 列的三行,−109+109+109=109-10^9+10^9+10^9=10^9。

数据范围

  • 1≤n,m≤1001\le n,m\le 100;
  • 1≤q≤10001\le q\le 1000;
  • −109≤ai,j≤109-10^9\le a_{i,j}\le 10^9;
  • 1≤r1≤r2≤n1\le r_1\le r_2\le n,1≤c1≤c2≤m1\le c_1\le c_2\le m,保证每次询问的矩形非空。

说明

  • 每次询问都必须包含 r1,r2r_1,r_2 两行和 c1,c2c_1,c_2 两列的边界元素,不能把闭区间当成半开区间。
  • 即使 r1=r2r_1=r_2 或 c1=c2c_1=c_2,询问依然合法:前者表示一行,后者表示一列,两者都成立时表示一个格子。
  • 单个答案的绝对值最大可达 100×100×109=1013100\times 100\times 10^9=10^{13},超出 3232 位整数范围,请用 long long 等 6464 位整数保存累加结果。
  • 在本题数据范围内,对每次询问直接枚举它覆盖的格子并累加即可通过(最坏 q⋅n⋅m≤107q\cdot n\cdot m\le 10^7 次加法),不要求使用二维前缀和或二维差分。

2026级SYUCT-ACM新生第四次训练

未参加
状态
已结束
规则
XCPC
题目
40
开始于
2026-10-30 18:30
结束于
2026-11-16 10:30
持续时间
400 小时
主持人
参赛人数
62