791 . 都市更新
TopCoder
Description
在一塊方方正正的土地中，市長準備進行都市更新。這塊土地是 $N\times M$ 的矩形，左上角座標 $(0,0)$，左下角座標 $(N-1, 0)$，右上角座標 $(0, M-1)$，右下角座標 $(N-1, M-1)$。每一個座標 $(i, j)$ 的位置都有一棟價值 $a_{ij}$ 的建築物，一旦這個位置被都更，這棟建築就要被剷平。
市長想選一塊方正的矩形區域作為都更預定地，其中左上角為 $(u,l)$，右下角為 $(d, r)$，矩形兩軸平行都市邊界。他一共會提出 $Q$ 種方案，想問你每種方案分別要剷除多少價值的建築物。
Input Format
輸入第一行是三個以空白分隔的整數 $N, M, Q$，分別代表都市的長寬和市長提出的方案數。
接下來有 $N$ 行每行 $M$ 個以空白分割的整數，其中第 $i$ 行第 $j$ 個數字表示 $a_{i-1, j-1}$。
接下來 $Q$ 行，每行四個以空白分割的整數 $u, l, d, r$，代表市長提出的都更方案。
輸入保證 $1\le N, M\le 500$，$1\le a_{ij}\le 10^ 9$，$1\le Q\le 300000$，$0\le u \le d < N$，$0\le l \le r < M$。
Output Format
輸出 $Q$ 行，每行包含一個整數，代表該筆詢問需要剷除建築的價值。
Sample Input 1
2 3 2
1 3 5
2 4 6
0 0 1 1
0 1 1 1
1 3 5
2 4 6
0 0 1 1
0 1 1 1
Sample Output 1
10
7
7
Sample Input 2
3 3 3
1 3 5
6 8 7
2 4 9
1 1 2 1
0 1 2 2
0 0 2 2
1 3 5
6 8 7
2 4 9
1 1 2 1
0 1 2 2
0 0 2 2
Sample Output 2
12
36
45
36
45
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~14 | 無額外限制 | 100 |