Codeforces Round #395 (Div. 1) E. Timofey and our friends animals
snuke さんの以下の記事を読んでいればやるだけ?
http://codeforces.com/contest/763/problem/E
問題概要
n 頂点のグラフが与えられる。頂点番号が[l,r]であるものだけを取り出したとき、連結成分がいくつあるか、というクエリが Q 個与えられるので順次処理せよ。
解法
平方分割。k≦5 という条件があるため、各頂点の次数は 10 以下で抑えられる。
あとは snuke さんの平方分割を適用するだけ。undo 可能な union find が作れることは割と自明だろう。経路圧縮は意味を成さないし、定数倍を悪化させるだけなのでやめておこう。
3416 ms。