Ma Trận Tổng Tiền Tố 2D
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho ma trận $N \times M$ số nguyên. Trả lời $Q$ truy vấn, mỗi truy vấn cho $(r_1, c_1, r_2, c_2)$, tính tổng các phần tử trong hình chữ nhật con từ $(r_1, c_1)$ đến $(r_2, c_2)$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$ $(1 \le N, M \le 1000)$.
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $(|a_{ij}| \le 10^6)$.
- Dòng tiếp theo chứa số nguyên $Q$ $(1 \le Q \le 10^5)$.
- $Q$ dòng tiếp theo, mỗi dòng chứa $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)$.
Dữ liệu ra
- Với mỗi truy vấn, in ra tổng trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 3 3 1 2 3 4 5 6 7 8 9 2 1 1 2 2 1 1 3 3 |
12 45 |
Giới hạn
- $1 \le N, M \le 1000$
- $|a_{ij}| \le 10^6$
- $1 \le Q \le 10^5$
Community Discussion