yukicoder No.307 最近色塗る問題多くない？ の計算量

唐突に解説を書きたくなったのでブログを生やしました。
嘘解法かと思って投げたのが想定解だった。

問題

No.307 最近色塗る問題多くない？ - yukicoder

回答

http://yukicoder.me/submissions/60722

解説

writer解説
http://yukicoder.me/problems/769/editorial

想定解が計算量的になんとかなることの説明をします。

あるマスが回色が変わると全てのマスが同じ色になります。(コドフェス2015リレーHっぽい)

よって、クエリで塗り替えられたマスの数の和がになると、鳩ノ巣原理より、あるマスは回以上色が変わるので、全てのマスが同じ色になっているはずです。

計算量は幅優先探索でマスの色を変える回数に比例するのと、クエリを読む分を合わせてになります。