Cập nhật và truy vấn hình chữ nhật 2D

Arrays Buổi 15 — Prefix Sum & Difference Array prefix-sum
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho ma trận kích thước $N \times M$ ban đầu toàn số $0$. Đầu tiên thực hiện $U$ phép cập nhật: mỗi phép cộng thêm $V$ vào toàn bộ hình chữ nhật con $(r_1, c_1, r_2, c_2)$. Sau khi thực hiện xong toàn bộ $U$ phép cập nhật, hãy trả lời $Q$ truy vấn: mỗi truy vấn yêu cầu tính tổng các phần tử trong hình chữ nhật con $(r_1, c_1, r_2, c_2)$.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên $N, M, U, Q$. $U$ dòng tiếp theo, mỗi dòng chứa 5 số nguyên $r_1, c_1, r_2, c_2, V$. $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 2
1 1 2 3 2
2 2 3 4 -1
1 1 2 2
2 2 3 4
7
-2
2 2 1 2
1 1 2 2 5
1 1 2 2
1 2 2 2
20
10
Giới hạn

$1 \le N, M \le 1000$, $0 \le U \le 10^5$, $1 \le Q \le 10^5$, $|V| \le 10^6$.

Draft saved