Dynamic connectivity contest: Connect and Disconnect

こんなコンテストがあったんですね。

問題ページ

問題概要

1. 辺の追加
2. 辺の削除
3. 連結成分の個数を求める

という 3 種類のクエリが与えられるので順次処理せよ。

解法

オフライン dynamic connectivity。anta さんの wiki を参考にした。

Decomposable searching problem - オフラインの場合 - yukicoder

辺 e の追加タイミングを左端、削除タイミングを右端とした区間を考えると、非遅延セグメント木の要領で dynamic connectivity を実現できる。

undo を実装するには操作履歴を stack に積んでおけばいい。

前作った dynamic connectivity は当然のごとく MLE した。何とかしたいなぁ…。