Flipping Puzzle

解説

この問題について、以下のことが言えます。

• ある $x, y$ を $2$ 回以上選ぶ必要はない。
• $x, y$ を選ぶ順番は考慮する必要がない。

また、以下のような順で操作を行うことが最適です。

• $(x, y) = (1, 1), (1, 2), (1, 3), \cdots, (1, W-1), (2, 1), (2, 2), \cdots, (H-1, W-1)$ の順で走査する。
• マス $(x, y)$ が黒色に塗られていた場合に操作を行う。
• $y = W-1$ が終了した時点でマス $(x, W)$ が黒色に塗られていた場合、不可能である。
• 全ての走査が終わった際に、黒色に塗られているマスが残っている場合、不可能である。

このように処理を行い操作回数を数えることで、最小の操作回数を求めることができます。
しかしながら、愚直にこのように実装をすると $O(HW)$ の計算量が必要になり、実行時間に間に合いません。

ここで、マス$(x-1, W-1)$ までの走査が終わっている状態で、 マス $(x, y_1), $ マス $(x, y_2), \cdots , $ マス $(x, y_{k})$ が黒色のマスであるとします。 ここで、 $k$ が奇数である場合はその列を全て白色にすることが不可能ですので -1 を出力して終了させます。

すると、操作を行う必要があるマスは、マス $(x, y_1)$ からマス $(x, y_2 - 1)$ までと、マス $(x, y_3)$ からマス $(x, y_4-1)$ までと、 $\cdots$、 マス $(x, y_{k-1})$ からマス $(x, y_k-1)$ までの $k/2$ 区間となります。

そして、$G[y] := ($マス $(x, y)$ で操作を行う必要があるならば $1$、そうでなければ $0)$ を考えることで、その情報は区間 XOR 区間和の遅延評価セグメント木に乗せることができます。

全ての走査が終了した段階で、総和が $0$ のときに操作回数の合計を出力し、そうでなければ -1 を出力することで答えを求めることができます。