Truy vấn tổng ma trận con 2D
Points
17
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Cho ma trận số nguyên kích thước $N \times M$ (các hàng đánh số từ $1$ đến $N$, các cột từ $1$ đến $M$) và $Q$ truy vấn. Mỗi truy vấn gồm 4 số nguyên $r_1, c_1, r_2, c_2$ ($1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le M$), yêu cầu tính tổng các phần tử trong hình chữ nhật con có góc trên trái $(r_1, c_1)$ và góc dưới phải $(r_2, c_2)$.
Dữ liệu vào
Dòng đầu chứa ba số nguyên $N, M, Q$. $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên. $Q$ dòng cuối cùng, mỗi dòng chứa 4 số nguyên $r_1, c_1, r_2, c_2$.
Dữ liệu ra
Với mỗi truy vấn, in ra tổng hình chữ nhật con tương ứng trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 3 4 2 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 2 2 2 3 4 |
14 54 |
| 2 2 2 -1 2 3 -4 1 1 2 2 1 2 2 2 |
0 -2 |
Giới hạn
$1 \le N, M \le 1000$, $1 \le Q \le 10^5$, $|A_{i,j}| \le 10^9$.
Community Discussion