緑色のマスの数を \(N\) 個として、それぞれマス \(0,1,\dots N-1\) とラベリングします。

\(C(l,r)\) を \(l\) 以上 \(r\) 未満のマスを赤く塗ったときの連結成分の個数とします。

すると、 \(C(0,1),C(1,2),\dots C(N-1,N)\) が分かれば答えがもとまります。

これを愚直に求めると TLE しますが、分割統治法と undo 付き UFtree を用いると高速に求めることができます。

まず、\(C(0,N)=0\) です。 \(C(l,r)\) の連結の仕方がわかっているとき、\(m=(l+r)/2\) として、 \(C(l,m)\),\(C(m,r)\) の連結の仕方は undo 付き Union Find を用いて、 \(O((r-l)\log(r-l))\) で求められます。

よって、 \(C(l,r)\) から \(C(l,m)\) の状態を探索した後、 \(C(l,r)\) に戻して \(C(m,r)\) の状態を探索して前に戻るということを再帰的に繰り返したら良いです。

時間計算量は \(O(HW\log(HW)^{2})\) です。

c++ 実装例 865ms