Editorial for Dynamic Connectivity
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Chia các truy vấn thành ~\sqrt{n}~ nhóm, khi xét đến nhóm thứ ~i~:
hợp nhất các cạnh được thêm trước nhóm ~i~ mà có thời điểm xóa sau nhóm ~i~.
khi xét đến thao tác thứ ~j~ trong nhóm thứ ~i~, ta lưu những cạnh được thêm mà có thời điểm xóa nằm trong nhóm ~i~ và lớn hơn ~j~.
với mỗi cạnh ~(u, v)~ được lưu, gọi ~tplt(u)~ là chỉ số của thành phần liên thông chứa ~u~. Nếu ~u~ và ~v~ nằm ở 2 thành phần liên thông khác nhau ta thêm 1 cạnh giữa ~tplt(u)~ và ~tplt(v)~ trong đồ thị ảo.
Dễ thấy, khi này đáp án cho truy vấn chính là số thành phần liên thông trong cây DSU - (số đỉnh - số thành phần liên thông trong đồ thị ảo). Độ phức tạp ~O(n \times \sqrt{n})~
Comments