#O1010. 子矩阵和

子矩阵和

子矩阵和

题目描述

给定一个 nn 行 mm 列的整数矩阵 AA,共有 qq 次询问。每次询问给出 (x1,y1,x2,y2)(x_1, y_1, x_2, y_2),要求输出左上角为 (x1,y1)(x_1, y_1)、右下角为 (x2,y2)(x_2, y_2) 的子矩阵中所有元素之和。

输入格式

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

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

接下来 qq 行,每行四个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2。

输出格式

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

样例 #1

样例输入 #1

2 3 2
1 2 3
4 5 6
1 1 2 3
2 2 2 3

样例输出 #1

21
11

数据规模与约定

数据范围 n,mn, m qq Ai,jA_{i,j}
全部测试点 1≤n,m≤10001 \le n, m \le 1000 1≤q≤1051 \le q \le 10^5 −109≤Ai,j≤109-10^9 \le A_{i,j} \le 10^9
  • 矩阵规模最大 10610^6 个元素,输入数据可达 10710^7 字节级别。
  • 子矩阵和最大可达 101510^{15},请使用 64 位整数。
  • 保证 1≤x1≤x2≤n1 \le x_1 \le x_2 \le n,1≤y1≤y2≤m1 \le y_1 \le y_2 \le m。
  • 逐次询问暴力求和的时间复杂度为 O(q⋅n⋅m)O(q \cdot n \cdot m),在最大数据下必然超时。