Loại cây kỳ lạ
View as PDFGiáo sư Hà Phong của trường đại học Nevada vừa công bố một phát hiện khoa học mới về hành tinh XYZ. Công bố của ông đã cho thấy có tồn tại sự sống của một loài cây trên hành tinh XYZ. Sự tồn tại và phát triển của loại cây này rất kì lạ. Mỗi cây được lớn lên từ hai "mầm", hai "mầm" này sẽ đâm lên khỏi mặt đất với độ cao ~H~ vào một ngày nào đó và dừng lại ở đó không phát triển thêm nữa. Cây khi đâm lên khỏi mặt đất sẽ có dạng như một hình chữ nhật (xem Hình 1), hai cạnh bên được gọi là "vertical" cạnh bắc ngang được gọi là "horizontal". Mỗi cây trên hành tinh đó được biểu diễn bởi ba số: các tọa độ ~x~ của các "vertical" là ~L~ và ~R~, và độ cao ~H~.
Mỗi ngày có một cây mới mọc lên từ hành tinh. Mỗi cây mới mọc lên có chiều cao lớn hơn chiều cao của cây mọc lên ngày liền trước đó một đơn vị. Khi một cạnh "vertical" một cây mới giao với một cạnh "horizontal" một cây khác thì có một bông hoa tại điểm giao đó được nở ra với điều kiện giao điểm đó không phải là các đầu mút của cạnh "horizontal" và tại điểm đó chưa từng tồn tại bông hoa nào.
Yêu cầu: Cho biết tọa độ "vertical" của các cây mọc lên mỗi ngày, cây mọc lên trong ngày thứ nhất có chiều cao bằng 1. Hãy cho biết mỗi ngày có bao nhiêu bông hoa mới xuất hiện.
Dữ liệu vao:
- Dòng đầu tiên ghi một số nguyên ~n~ (1 ≤ ~n~ ≤ 100.000) là số ngày.
- ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L,R~ (1 ≤ ~L~ < ~R~ ≤ ~10^5~) là tọa độ các cạnh "vertical" của cây mọc lên vào ngày thứ ~i~.
Kết quả: Ghi ra ~n~ dòng, dòng thứ ~i~ là số bông hoa mới được nở ra trong ngày thứ ~i~.
Vi du:
INPUT 1
4
1 4
3 7
1 6
2 6
OUTPUT 1
0
1
1
2
INPUT 2
5
1 3
3 5
3 9
2 4
3 8
OUTPUT 2
0
0
0
3
2
Ràng buộc:
- Có 25% số test tương ứng 25% số điểm có ~n~ ≤ 5000, ~R~ ≤ 5000;
- Có 25% số test khác tương ứng 25% số điểm có ~n~ ≤ 5000, ~R~ ≤ ~10^6~;
- Có 25% số test khác tương ứng với 25% số điểm có ~n~ ≤ 50000,~R~ ≤ 250;
- 25% số test còn lại tương ứng 25% số điểm có ~n~ ≤ ~10^5~, ~R~ ≤ ~10^5~.
Comments
Mình xin đóng góp lời giải của bài này :
Nhận xét :
Tại ngày thứ i, số bông hoa được tạo ra thêm bằng số giao điểm giữa hai cạnh dọc của ngày thứ i (Li, Ri) với các cạnh ngang của các ngày trước đó.
Vì số bông hoa đã được tạo ra rồi sẽ không được tính nữa (nếu tọa độ bông hoa là giao điểm) nên ta chú ý trừ đi cho thích hợp.
Ý tưởng : Với mỗi đoạn Li, Ri ta sẽ phủ được đoạn Li + 1 -> Ri – 1.
(Vì trục của ngày sau luôn lớn hơn ngày trước 1 đơn vị, nên ta chỉ cần quan tâm hoành độ Li và Ri).
Ta dễ thấy rằng số bông hoa mới được tạo ra sẽ là số giao điểm giữa Li, Ri với các cạnh ngang trước đó hay nói cách khác là số lần được phủ (và chưa có hoa) tại hai điểm Li và Ri.
Cách làm :
Gọi f[i] là số lần được phủ tại điểm i ( số cạnh ngang phủ được điểm i).
Mỗi ngày,
Số bông hoa mới được tạo ra sẽ là f[Li] + f[Ri].
Ta sẽ cập nhật f[i] bằng cách bỏ đi số bông hoa đã xuất hiện tại Li và Ri <=> f[Li] = f[Ri] = 0; (Xóa hết giao điểm tại Li, Ri)
Và tăng đoạn Li + 1 -> Ri – 1 lên 1.
Sub 1, 3 : (O(n * R))
Với mỗi Li, Ri
Res = f[Li] + f[Ri]
F[Li] = F[Ri] = 0;
Duyệt : i – (Li + 1 -> Ri – 1), f[i] += 1;
Sub 4 : (O(n * LogR))
Vẫn với ý tưởng trên, ta sẽ giảm chi phí tính cập nhật f[] từ O(R) xuống O(logR).
Để làm được như thế ta sẽ sử dụng CTDL Segment Tree và kĩ thuật Lazy Update.
Bài toán chúng ta trở thành :
Thêm vào tất cả phần tử thuộc đoạn L, R một giá trị Val. Tính giá trị tại vị trí Pos.
Các bạn có thể tham khảo cách làm này tại đây : https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md#2-lazy-propagation