子矩阵和
题目描述
给定一个 n 行 m 列的整数矩阵 A,共有 q 次询问。每次询问给出 (x1,y1,x2,y2),要求输出左上角为 (x1,y1)、右下角为 (x2,y2) 的子矩阵中所有元素之和。
输入格式
第一行三个整数 n,m,q。
接下来 n 行,每行 m 个整数,表示矩阵 A。
接下来 q 行,每行四个整数 x1,y1,x2,y2。
输出格式
共 q 行,每行一个整数,表示对应子矩阵的元素之和。
样例 #1
样例输入 #1
2 3 2
1 2 3
4 5 6
1 1 2 3
2 2 2 3
样例输出 #1
21
11
数据规模与约定
| 数据范围 |
n,m |
q |
Ai,j |
| 全部测试点 |
1≤n,m≤1000 |
1≤q≤105 |
−109≤Ai,j≤109 |
- 矩阵规模最大 106 个元素,输入数据可达 107 字节级别。
- 子矩阵和最大可达 1015,请使用 64 位整数。
- 保证 1≤x1≤x2≤n,1≤y1≤y2≤m。
- 逐次询问暴力求和的时间复杂度为 O(q⋅n⋅m),在最大数据下必然超时。