Tổng hình chữ nhật trên ma trận

Buổi 04 — Mảng 2D & Chuỗi prefix-sum
Points
16
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Submissions
Đề bài

Cho ma trận số nguyên $A$ kích thước $M \times N$ (đánh số từ $1$) 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 M$, $1 \le c_1 \le c_2 \le N$), yêu cầu tính tổng các phần tử trong ma trận con có góc trên-trái là $(r_1, c_1)$ và góc dưới-phải là $(r_2, c_2)$.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên dương $M, N, Q$.
  • $M$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên.
  • $Q$ dòng cuối cùng, mỗi dòng chứa bốn số nguyên $r_1, c_1, r_2, c_2$.
Dữ liệu ra

Gồm $Q$ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Ví dụ
Input Output
3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3
12
28
Giới hạn

$1 \le M, N \le 1000$, $1 \le Q \le 10^5$, $|A_{i,j}| \le 10^9$.

Draft saved