#O1087. 子矩阵和

子矩阵和

题目描述

给定一个 nn 行 mm 列的整数矩阵,有 qq 次询问,每次询问一个子矩阵的和。

输入格式

第一行三个整数 n,m,qn,m,q。

接下来 nn 行,每行 mm 个整数,表示矩阵。

接下来 qq 行,每行四个整数 x1,x2,y1,y2x_1,x_2,y_1,y_2,表示询问第 x1x_1 到 x2x_2 行、第 y1y_1 到 y2y_2 列的子矩阵。

输出格式

共 qq 行,每行一个整数,表示对应子矩阵的和。

样例 #1

样例输入 #1

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

样例输出 #1

12
28

数据规模与约定

数据范围 说明
1≤n,m≤20001 \le n,m \le 2000 矩阵规模
1≤q≤10001 \le q \le 1000 询问个数
−100≤ai,j≤100-100 \le a_{i,j} \le 100 元素
  • 二维前缀和,单次询问 O(1)O(1)。