AGC015 C. Nuske vs Phantom Thnook - phyllo’s algorithm note

N*Mのグリッドの各マスに色が塗ってある。
ある色の塗ってあるマスから別の色の塗ってあるマスへ移動できる場合、同じマスを通らずに移動する経路は高々1通りである。

Q個のクエリが与えられる。
各クエリは「(x1,y1)から(x2,y2)の長方形範囲でグリッドを切り出したとき、色の塗ってあるマスの連結成分がいくつあるか？」の質問であるので、これに答えよ。

1 <= N,M <= 2000
1 <= Q <= 200,000

どこから考えるかが難しい。

問題の最初の条件は「森(グラフ理論)」のことを言っている。
任意のグラフで連結成分を求めるにはUnionFindなどが使えるが、森における連結成分は「頂点数 - 辺の数」で求められる。

頂点数は、単純に2次元累積和で求められる。
辺の数も、各頂点に対して下方向か右方向にしか伸びないので、同様に2次元累積和で求められる(縦方向の辺、横方向の辺で独立に累積和を計算すると見通しがよい)。

計算量は、構築がO(NM)でクエリ処理がO(Q)なので、全体でO(NM+Q)。