Dynamic connectivity contest: Bridges: The Final Battle

http://codeforces.com/gym/100551/problem/D

問題概要

辺の追加・削除のクエリが与えられる。クエリを処理する毎に橋の個数を出力せよ。

• 1≦N,K≦10⁵

解法

以下記事で紹介されているテクニックを適用する。

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

同じ時間に ADD/DEL が複数回呼び出されないため、サイズ N のノードには高々 N 個のアイテムしか追加されない。したがって、そのノードの配下には高々 NlogN 個のアイテムしか存在しないことがわかる。

セグメント木を巡回する際、各ノードで二重辺連結成分分解をおこない木を作る。そして、配下にあるアイテムに関係のない頂点を縮約する。このようにすることで各ノードでの頂点の個数が O(NlogN) になる。

計算量は T(n)=2T(n/2)+O(nlogn)=O(nlog² n)。もっと強く抑えられるかは知らない。

思いつくのに随分時間が掛かってしまった…。