offline_dynamic_connectivity

struct offline_dynamic_connectivity;

概要

辺の追加・削除を先読みして処理するオフライン動的連結性

add / erase を時刻順に登録してから build と solve を呼ぶ。

前処理はイベント数を $k$ として $O(k\log(k+q))$、 solve は $O((q+k\log q)\log n)$（コールバックの実行時間を除く）

名前	説明	計算量
`(constructor)`	`n` 頂点・`q` 時刻の問い合わせを処理するオブジェクトを作る	$O(n+q)$

名前	説明	計算量
`add`	時刻 `t` に無向辺 `(u, v)` を追加するイベントを登録する	$O(\log k)$
`erase`	時刻 `t` に無向辺 `(u, v)` を削除するイベントを登録する	$O(\log k)$
`build`	登録したイベントから各辺が有効な時刻区間を構築する	イベント数を $k$ として $O(k\log(k+q))$
`solve`	各時刻のグラフ状態を復元し、`query(t)` を呼ぶ	$O((q+k\log q)\log n)$（`query` の実行時間を除く）
`same`	現在復元中の時刻で `u`, `v` が連結なら true を返す	$O(\log n)$