Phủ điểm 2
Đề 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.
2
1 1 2 2
1 1 3 39Giả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ày chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
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.
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ô.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ủ.
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á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ô.
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.lower_bound(xs.begin(), xs.end(), X1[i]) - xs.begin()trả về vị trí củaX1[i]trongxs(giá trị này chắc chắn có trongxs).- Số điểm có thể tới gần $10^{10}$ nên nhân bằng
1LL * ...và cộng vào biếnlong long. - Tên biến không đặt là
y1vì<bits/stdc++.h>đã có sẵn hàmy1()(hàm Bessel trong<cmath>), khai báo mảng toàn cục têny1sẽ bị lỗi biên dịch. Mình dùng chữ hoaX1, Y1, X2, Y2.
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:
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:
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.