Truy Vấn Tổng Hình Chữ Nhật Con 2D Prefix Sum O(1)
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Đề bài
Cho bảng số kích thước N × M (chỉ số hàng từ 1..N, cột từ 1..M) và Q truy vấn. Mỗi truy vấn gồm 4 số nguyên r1, c1, r2, c2 (1 ≤ r1 ≤ r2 ≤ N, 1 ≤ c1 ≤ c2 ≤ M), yêu cầu tính tổng tất cả các phần tử nằm trong hình chữ nhật con có góc trên trái (r1, c1) và góc dưới phải (r2, c2).
Dữ liệu vào (Input)
- Dòng 1: Ba số nguyên dương
N, M, Q(1 ≤ N, M ≤ 500,1 ≤ Q ≤ 10^5). Ndòng tiếp theo: Mỗi dòng gồmMsố nguyênA[i][j].Qdòng tiếp theo: Mỗi dòng gồm 4 số nguyênr1 c1 r2 c2.
Dữ liệu ra (Output)
- Gồm
Qdòng, mỗi dòng là tổng hình chữ nhật con tương ứng.
Ví dụ mẫu
Sample Input 1
3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3
Sample Output 1
12
28
Community Discussion