2408. 二维前缀和【模板】
1000ms
256MB
简单
前缀和与差分
模板题
题目描述
输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个询问，每个询问包含四个整数 $x_1, y_1, x_2, y_2$，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问，输出子矩阵中所有数的和。
输入格式
- 第一行包含三个整数 $n, m, q$。
- 接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。
- 接下来 $q$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，表示一组询问。
输出格式
- 共 $q$ 行，每行输出一个询问的结果。
样例 1
输入 (Input)
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
输出 (Output)
17 27 21
- $1 \le n, m \le 1000$
- $1 \le q \le 200,000$
- $1 \le x_1 \le x_2 \le n$
- $1 \le y_1 \le y_2 \le m$
- $-1000 \le$ 矩阵内元素的值 $\le 1000$
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功