h288. 地图区域总量

题目描述

给定一个 $n$ 行 $m$ 列的非负整数矩阵，并回答 $q$ 次查询。每次查询给出左上角 $(x_1,y_1)$ 和右下角 $(x_2,y_2)$，求这个闭合子矩形内所有元素的和。

行、列下标均从 $1$ 开始。

输入格式

第一行输入三个整数 $n,m,q$。

接下来 $n$ 行，每行输入 $m$ 个整数。

接下来 $q$ 行，每行输入四个整数 $x_1,y_1,x_2,y_2$。

输出格式

对每次查询输出一行答案。

数据范围

• $1\le n,m\le 500$
• $1\le q\le 100000$
• $0\le a_{i,j}\le 1000$
• $1\le x_1\le x_2\le n$
• $1\le y_1\le y_2\le m$

样例

3 4 3
1 2 3 4
5 6 7 8
9 10 11 12
1 1 2 2
2 3 3 4
3 2 3 2

14
38
10

标签：二维前缀和、矩阵