Codeforces Round #395 (Div. 1) E. Timofey and our friends animals

snuke さんの以下の記事を読んでいればやるだけ？

n 頂点のグラフが与えられる。頂点番号が[l,r]であるものだけを取り出したとき、連結成分がいくつあるか、というクエリが Q 個与えられるので順次処理せよ。

平方分割。k≦5 という条件があるため、各頂点の次数は 10 以下で抑えられる。

あとは snuke さんの平方分割を適用するだけ。undo 可能な union find が作れることは割と自明だろう。経路圧縮は意味を成さないし、定数倍を悪化させるだけなのでやめておこう。

3416 ms。