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.

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

Please read the guidelines before commenting.


There are no comments at the moment.