Rectangle Sum Queries
Answer Q sum queries over sub-rectangles of an N×M grid: each query gives the top-left (r1, c1) and bottom-right (r2, c2).
Input: the first line has N, M and Q; the next N lines have the grid; the next Q lines have r1 c1 r2 c2.
Output: Q lines with the rectangle sums.
Constraints:
- 1 ≤ N, M ≤ 500
- 1 ≤ Q ≤ 104
Sample Tests
Input 1
2 2 1 1 2 3 4 1 1 2 2
Output 1
10
Input 2
1 1 1 5 1 1 1 1
Output 2
5
Discussion (opens after you solve — no spoilers before)
No comments yet.