trang chủ / đề bài / diff2d / lời giải

Cập nhật hình chữ nhật

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả:

huunguyen

Hướng tiếp cận

Đây là phiên bản 2D của kỹ thuật mảng hiệu. Mỗi thao tác cập nhật hình chữ nhật $(r_{1}, c_{1}, r_{2}, c_{2}, v)$ được mã hóa bằng bốn dấu chấm trên mảng hiệu $d$ , sau đó lấy tổng tiền tố 2D một lần duy nhất là khôi phục được ma trận $A$ .

Nhận xét quan trọng

Nếu cộng trực tiếp lên mọi ô của hình chữ nhật thì chi phí mỗi thao tác là $O (n \cdot m)$ , tổng chi phí lên tới $O (q \cdot n \cdot m) \approx 2 \cdot 10^{11}$ — không thể chấp nhận.
Với mảng hiệu 1D, để cộng $v$ trên đoạn $[l, r]$ ta làm $d [l] + = v$ và $d [r + 1] - = v$ . Mở rộng lên 2D, để cộng $v$ trên hình chữ nhật $[r_{1} . . r_{2}] \times [c_{1} . . c_{2}]$ ta dùng nguyên lý bao hàm – loại trừ trên bốn góc.
Toàn bộ giá trị có thể đạt cỡ $q \cdot v_{max} \approx 2 \cdot 10^{14}$ , phải dùng long long.

Thuật toán

Dựng mảng $d [0 . . n + 1] [0 . . m + 1]$ khởi tạo bằng $0$ . Với mỗi thao tác $(r_{1}, c_{1}, r_{2}, c_{2}, v)$ :

$d [r_{1}] [c_{1}] + = v$
$d [r_{1}] [c_{2} + 1] - = v$
$d [r_{2} + 1] [c_{1}] - = v$
$d [r_{2} + 1] [c_{2} + 1] + = v$

Sau đó dựng tổng tiền tố 2D ngay trên $d$ (in-place): với $1 \leq i \leq n$ , $1 \leq j \leq m$ ,

$d [i] [j] + = d [i - 1] [j] + d [i] [j - 1] - d [i - 1] [j - 1] .$

Khi đó $A [i] [j] = d [i] [j]$ . Trả lời mỗi truy vấn điểm $(r, c)$ trong $O (1)$ .

Độ phức tạp

Thời gian: $O (q + n \cdot m + k)$ .
Bộ nhớ: $O (n \cdot m)$ cho mảng hiệu / tổng tiền tố.

Bình luận

Không có bình luận tại thời điểm này.