Phủ điểm 2

Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều (tham khảo MarisaOJ) Độ khó: Khá Mảng 2 chiều Nén toạ độ Mảng hiệu 2 chiều

Đề bài

Cho $n$ hình chữ nhật nằm trên mặt phẳng Đề-các. Hình thứ $i$ có góc trái dưới là $(x_1, y_1)$, góc phải trên là $(x_2, y_2)$. Đếm số lượng điểm nằm trong ít nhất 1 hình chữ nhật.

Input:

• Dòng đầu tiên gồm 1 số nguyên $n$.
• $n$ dòng tiếp theo mỗi dòng gồm 4 số nguyên $x_1, y_1, x_2, y_2$.

Output: in ra số lượng điểm nằm trong ít nhất một hình chữ nhật.

Điều kiện: $1 \le n \le 1000$; $1 \le x_1, y_1, x_2, y_2 \le 100\,000$.

Nguồn bài: tham khảo từ trang MarisaOJ và có chỉnh sửa lại.

Ví dụ – input

2
1 1 2 2
1 1 3 3

Ví dụ – output

9

Giải thích ví dụ: "điểm" ở đây là điểm có toạ độ nguyên, và điểm nằm trên cạnh cũng tính là nằm trong hình. Hình $(1,1)$–$(3,3)$ chứa $3 \times 3 = 9$ điểm, hình $(1,1)$–$(2,2)$ nằm gọn bên trong nó, nên đáp án là $9$.

Lời mở đầu

Ở bài "Phủ điểm" bản 1, toạ độ nhỏ nên ta có thể tô thẳng lên một mảng 2 chiều. Sang bản 2 này toạ độ lên tới $10^5$: một mảng $10^5 \times 10^5$ cần tới $10^{10}$ ô – không máy chấm nào chứa nổi. Nhưng chỉ có $1000$ hình, tức là chỉ có tối đa $2000$ toạ độ "đáng chú ý" mỗi chiều. Bài này là dịp rất tốt để học nén toạ độ và mảng hiệu 2 chiều – hai kỹ thuật dùng lại rất nhiều về sau.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testCách 1Tô từng điểmÝ tưởngNén toạ độCách 2Tô từng khốiCách 3Mảng hiệu 2D

Bộ testBộ test chính thức có gì?

Bộ test có 100 test. Đề không ghi subtask, nhưng bộ test chia rất rõ thành 2 mức:

Test	n	Toạ độ	Số mốc x / y (max)	Số test có hình suy biến	Đáp án
1 – 20	2 … 10	1 … 20	15 / 15	13	9 … 336
21 – 100	1000 … 1000	1 … 99 999	1 579 / 1 598	0	9 550 782 575 … 9 967 072 649

• Test 1 – 20: rất nhỏ, $n \le 10$, mọi toạ độ $\le 20$. Có 13 test chứa hình suy biến (đoạn thẳng hoặc một điểm, $x_1 = x_2$ hoặc $y_1 = y_2$) – đây là chỗ bắt lỗi ai quên rằng điểm trên cạnh cũng được tính.
• Test 21 – 100: đều có $n = 1000$, toạ độ trải gần hết $[1, 10^5]$, các hình rất to nên đáp án gần $10^{10}$ → phải dùng long long.
• Mọi hình đều có $x_1 \le x_2$, $y_1 \le y_2$ (không có hình bị "lật").

Mình tạm gọi 2 mức là "subtask" để so sánh các cách giải:

Mức	Điều kiện	Test	Cách 1	Cách 2	Cách 3
1 (20%)	$n \le 10$, toạ độ $\le 20$	1 – 20	✔	✔	✔
2 (80%)	$n = 1000$, toạ độ tới $10^5$	21 – 100	✘	✔	✔

Cách 1Tô từng điểm – chỉ ăn test nhỏ

Hình $(x_1, y_1)$–$(x_2, y_2)$ chứa đúng các điểm nguyên $(x, y)$ với $x_1 \le x \le x_2$ và $y_1 \le y \le y_2$, tức là $(x_2 - x_1 + 1) \cdot (y_2 - y_1 + 1)$ điểm. Cách đơn giản nhất: dùng mảng phu[x][y], với mỗi hình thì tô true mọi điểm của nó, cuối cùng đếm số ô true. Điểm bị nhiều hình phủ thì vẫn chỉ là một ô true, nên không bị đếm trùng.

C++▶ Chạy tay từng dòng codeCách 1: tô true mọi điểm của từng hình rồi đếm số ô true.

Dữ liệu vào (stdin) – sửa thoải mái2 1 1 2 2 1 1 3 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Để chạy tay được, khung này đổi MAXC = 1005 thành MAXC = 6 (toạ độ từ 1 đến 5). Ô xanh: điểm đã tô, ô tím: điểm của hình đang xét chưa tô.

Không gian$O(C^2)$ với $C$ là toạ độ lớn nhất

Thời gian$O(n \cdot C^2)$

Kết quả chạy thật: bản C++ đúng 20/100 test: qua trọn mức 1 (test 1 – 20). Từ test 21 toạ độ vượt 1000, chương trình ghi ra ngoài mảng và bị lỗi chạy (Runtime Error). Muốn nới mảng lên $10^5 \times 10^5$ thì cần khoảng 10 GB bộ nhớ – không thể. Bản Python cũng đúng 20/100.

Ý tưởngNén toạ độ: gom điểm thành từng khối

Hãy nhìn theo trục $x$. Mỗi hình chữ nhật phủ các cột $x_1, x_1 + 1, \ldots, x_2$, tức là nửa khoảng $[x_1,\ x_2 + 1)$. Nếu ta đánh dấu tất cả các "mốc" $x_1$ và $x_2 + 1$ của mọi hình rồi sắp xếp tăng dần thành mảng xs, thì giữa 2 mốc liên tiếp xs[u] và xs[u+1] không có hình nào bắt đầu hay kết thúc. Nghĩa là mọi cột trong dải $[xs[u],\ xs[u+1])$ được phủ giống hệt nhau.

Làm y như vậy với trục $y$ (mảng ys), mặt phẳng bị các mốc cắt thành một lưới các khối. Mỗi khối $(u, v)$ là một hình chữ nhật gồm $(xs[u+1] - xs[u]) \times (ys[v+1] - ys[v])$ điểm, và các điểm trong cùng 1 khối hoặc cùng được phủ, hoặc cùng không được phủ.

Nén toạ độ

Có tối đa $2n = 2000$ mốc mỗi chiều nên lưới khối chỉ có tối đa $2000 \times 2000 = 4 \cdot 10^6$ ô – vừa khít một mảng 2 chiều. Hình thứ $i$ phủ đúng các khối $u \in [a, b)$, $v \in [c, d)$ với $a, b, c, d$ là vị trí của $x_1,\ x_2 + 1,\ y_1,\ y_2 + 1$ trong xs, ys (tìm bằng lower_bound). Đáp án = tổng số điểm của các khối được phủ.

Vì sao lại là $x_2 + 1$ chứ không phải $x_2$? Vì cột $x_2$ vẫn thuộc hình, hình chỉ "kết thúc" ngay sau nó. Dùng nửa khoảng $[x_1, x_2 + 1)$ thì độ dài là $x_2 + 1 - x_1$, đúng bằng số cột, và hình suy biến thành đoạn thẳng ($x_1 = x_2$) cũng được xử lý tự nhiên – bộ test nhỏ có khá nhiều hình như vậy.

Em nhập các hình (mỗi hình 4 số x1 y1 x2 y2, các hình cách nhau dấu phẩy, toạ độ $\le 12$) rồi bấm Tiếp để xem các đường cắt và từng khối:

Các hình

Ví dụ nhanh:

Cách 2Nén toạ độ rồi tô từng khối – đã đủ điểm

Áp dụng ý tưởng trên một cách trực tiếp: với mỗi hình, tô true các khối $[a, b) \times [c, d)$ trên lưới nén, cuối cùng cộng diện tích (số điểm) của các khối được tô.

C++▶ Chạy tay từng dòng codeCách 2: nén toạ độ, tô từng khối của mỗi hình rồi cộng số điểm các khối được phủ.

Dữ liệu vào (stdin) – sửa thoải mái2 1 1 2 2 1 1 3 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Lưới vẽ như mặt phẳng: cột là chỉ số u (theo x), hàng là chỉ số v (theo y, tăng lên trên); mỗi ô ghi kèm khoảng toạ độ thật của khối.

1. sort + unique + erase: sắp xếp rồi xoá các mốc trùng nhau, đây là "công thức" nén toạ độ chuẩn.
2. lower_bound(xs.begin(), xs.end(), X1[i]) - xs.begin() trả về vị trí của X1[i] trong xs (giá trị này chắc chắn có trong xs).
3. Số điểm có thể tới gần $10^{10}$ nên nhân bằng 1LL * ... và cộng vào biến long long.
4. Tên biến không đặt là y1 vì <bits/stdc++.h> đã có sẵn hàm y1() (hàm Bessel trong <cmath>), khai báo mảng toàn cục tên y1 sẽ bị lỗi biên dịch. Mình dùng chữ hoa X1, Y1, X2, Y2.

Không gian$O(n^2)$

Thời gian$O(n \log n + n^3)$ trong trường hợp xấu nhất

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất khoảng 0,07 giây; bản Python (tô cả đoạn của một hàng bằng phép gán lát cắt) cũng đúng 100/100, chậm nhất khoảng 0,65 giây. Về lý thuyết đây là $O(n^3)$: mình tự sinh thêm test xấu nhất gồm 1000 hình lồng nhau $(i, i)$–$(10^5 - i, 10^5 - i)$, mỗi hình phủ gần hết lưới nén, tổng cộng khoảng $1{,}3 \cdot 10^9$ lần gán. Vậy mà C++ vẫn chỉ mất khoảng 0,08 giây, vì vòng lặp trong cùng là gán liên tiếp một dãy ô nhớ, trình biên dịch tối ưu thành lệnh memset cực nhanh. Tức là với $n \le 1000$ cách này vẫn qua, nhưng chỉ cần thêm một chút xử lý trong vòng lặp (ví dụ đếm số lần phủ) hoặc $n$ lớn hơn là hỏng – nên mình vẫn giới thiệu cách 3 chuẩn hơn.

Cách 3Mảng hiệu 2 chiều – O(n²)

Cách 2 tốn thời gian ở chỗ mỗi hình phải tô cả một vùng khối. Ta dùng lại mẹo của mảng hiệu (difference array): muốn cộng $1$ cho cả hình chữ nhật khối $[a, b) \times [c, d)$, chỉ cần sửa 4 góc:

Mảng hiệu 2 chiều

D[a][c]++; D[a][d]--; D[b][c]--; D[b][d]++;
Sau khi xử lý xong mọi hình, tính cộng dồn 2 chiều $D[u][v] \mathrel{+}$ $= D[u-1][v]$ $+ D[u][v-1] - D[u-1][v-1]$ thì $D[u][v]$ chính là số hình phủ khối $(u, v)$. Khối nào có $D[u][v] > 0$ thì cộng số điểm của khối đó vào đáp án.

Vì sao 4 góc là đủ? Khi cộng dồn, giá trị $+1$ ở góc $(a, c)$ "lan" sang mọi khối $(u, v)$ có $u \ge a, v \ge c$. Hai giá trị $-1$ ở $(a, d)$ và $(b, c)$ chặn sự lan đó ở bên phải cột $d$ và phía sau hàng $b$; vùng $u \ge b, v \ge d$ bị trừ 2 lần nên $+1$ ở $(b, d)$ bù lại. Kết quả: đúng vùng $[a, b) \times [c, d)$ được cộng 1.

Em bấm Tiếp để xem 4 góc của từng hình được ghi vào mảng D, rồi cộng dồn ra số hình phủ từng khối:

Các hình (tối đa 4)

Ví dụ nhanh:

C++▶ Chạy tay từng dòng codeCách 3: nén toạ độ + mảng hiệu 2 chiều, cộng dồn ra số hình phủ mỗi khối.

Dữ liệu vào (stdin) – sửa thoải mái2 1 1 2 2 1 1 3 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Hàng/cột "(chặn)" ứng với mốc lớn nhất: chỉ chứa các giá trị −1/+1 để chặn, không phải khối thật nên vòng lặp không duyệt tới.

Không gian$O(n^2)$

Thời gian$O(n \log n + n^2)$

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất khoảng 0,02 giây (test xấu nhất tự sinh ở trên cũng chỉ 0,02 giây). Bản Python đúng 100/100, chậm nhất khoảng 0,5 giây.

Ghi chú của mình: mọi kết quả ở trên là chạy thật trên đủ 100 test chính thức; thời gian là thời gian CPU đo trên máy của mình. Kỹ thuật nén toạ độ + mảng hiệu 2 chiều ở cách 3 dùng được cho cả những bài đếm "số lần phủ", "điểm được phủ đúng k lần"... chứ không chỉ "phủ ít nhất 1 lần" như bài này.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇