171. 子矩阵的和
时间限制：1000 MS 内存限制：64 MB
题目描述
# 子矩阵的和 ## 题目描述 给定一个 $n$ 行 $m$ 列的整数矩阵，以及 $q$ 个询问。 矩阵的行、列编号均从 $1$ 开始。每个询问包含四个整数 $x_1,y_1,x_2,y_2$，分别表示一个子矩阵的左上角坐标 $(x_1,y_1)$ 和右下角坐标 $(x_2,y_2)$，其中坐标的第一维表示行号，第二维表示列号。 对于每个询问，求出该子矩阵中所有元素的和。子矩阵包含其边界上的元素。 ## 输入格式 从文件 `matrix.in` 读入数据。 第一行包含三个整数 $n,m,q$，分别表示矩阵的行数、列数和询问次数。 接下来 $n$ 行，每行包含 $m$ 个整数，表示矩阵中对应行的元素。 接下来 $q$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一个询问的子矩阵左上角和右下角坐标。 ## 输出格式 输出到文件 `matrix.out`。 输出共 $q$ 行，按照输入中的询问顺序，每行输出一个整数，表示对应子矩阵中所有元素的和。 ## 数据范围 对于所有测试数据，满足： - $1 \le n,m \le 1000$； - $1 \le q \le 200000$； - $1 \le x_1 \le x_2 \le n$； - $1 \le y_1 \le y_2 \le m$； - 矩阵中的元素均为整数，取值范围为 $[-1000,1000]$； - 任意子矩阵中所有元素之和的绝对值不超过 $10^9$。 ## 样例输入 ``` 3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4 ``` ## 样例输出 ``` 17 27 21 ``` ## 资源限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。