Dynamic connectivity contest: Connect and Disconnect
こんなコンテストがあったんですね。
問題概要
- 辺の追加
- 辺の削除
- 連結成分の個数を求める
という 3 種類のクエリが与えられるので順次処理せよ。
解法
オフライン dynamic connectivity。anta さんの wiki を参考にした。
Decomposable searching problem - オフラインの場合 - yukicoder
辺 e の追加タイミングを左端、削除タイミングを右端とした区間を考えると、非遅延セグメント木の要領で dynamic connectivity を実現できる。
undo を実装するには操作履歴を stack に積んでおけばいい。
前作った dynamic connectivity は当然のごとく MLE した。何とかしたいなぁ…。