Link : https://marisaoj.com/problem/551
Vì solution khá dài và khó giải thích nên tác giả chỉ nêu những ý tưởng chính cho bài toán, còn phần implementation thì mình khuyến khích các bạn nên tự suy nghĩ vì đây là phần hay và khó nhất của một bài toán cấu trúc dữ liệu
Giả sử ta đang xét đường thẳng x = $idx$.
Ta có 1 đoạn thẳng có dạng $(idx,y1,idx,y2)$ thì điều kiện để đoạn thẳng này tạo ra một phần mới trên tờ giấy chính là đoạn thẳng phải cắt qua 2 đường thẳng mà trước đó đã được nổi với nhau theo bất kì cách nào


Như hình trên thì trong vùng màu vàng thì chỉ cần có cách nối 2 đường thẳng y1,y2 lại thì ta có thể tạo ra dc 1 hình mới trên tờ giấy.
Ví dụ như : Đường thẳng y1 được nối với y2 theo đường màu đỏ
Vậy làm sao để ta biết được 2 đoạn thẳng ngang nào đang được nối với nhau?
Câu trả lời rất đơn giản, mỗi lần có một đoạn thẳng dọc cắt qua $k$ đoạn ngang thì ta sẽ cho chúng vào một thành phần liên thông, thao tác này có thể được thực hiện bằng cấu trúc dữ liệu dsu.
Nếu trong đoạn đấy đang có 2 thành phần liên thông thì ta sẽ merge chúng lại vì giữa tất cả những đoạn thẳng ấy ta đều có cách để nối chúng đôi một với nhau.
Vậy làm sao để tính toán được đáp án?
Với mỗi đoạn thẳng dọc, khi ta cắt 2 cặp đoạn thẳng ngang đang nối với nhau "liên tiếp" thì chúng sẽ tạo ra một phần mới trên trang giấy.
Tại sao lại là liên tiếp thì mời bạn đọc tự chứng minh.
Ở đây có 3 đoạn thẳng đang nối với nhau liên tiếp nên sẽ tạo ra 2 phần mới trên tờ giấy.
Việc tính quản lí các đoạn được nối với nhau và tính toán đáp án có thể được thực hiện bằng bit + set.
Đpt sẽ là $o(n \times log(n))$