(writer : kyopro_friends, 解説 : sataashun)

初め、盤面は以下の画像のようになっています (便宜上\(H, W\) で縦横を表していますが、初めは \(H=W=N\) です)。青い枠が黒い石を、赤い斜線部が白い石を表します。

向きの違うクエリ同士が影響を及ぼし合うため複雑そうですが、この盤面に \((1, x)\) のクエリが来たとしましょう (\((2, x)\) も同様です)。\(2 \leq x \leq W\) を仮定すると、以下の図のような状況になります。

このとき、\(j\) 列目 (\(x + 1 \leq j < W)\) については、それ以降横向き (\((2, x)\) の形)のクエリが関係しないことがわかります。この紫の枠の中の範囲を、\(1\) つ目の画像だと思って残りのクエリを処理していきます。

先程クエリに対して \(2 \leq x \leq W\) を仮定しましたが、残りの \(x\) の範囲については、この枠を縮める操作の仮定で、\(b_x := \) \(x\) 列目にある白石の中で最も手前にあるものの座標 を求めておくと、裏返る石の個数を \(\mathrm{O}(1)\) で求めることができます。

同様に行についても同様の情報 \((a)\) を保持し、各クエリについてはその線分が現在の枠の中であれば枠を縮めながら、\(a\) または \(b\) を更新していけばよいです。

時間計算量ですが、\(a, b\) の各要素は枠の外に出るタイミングでのみ更新されるので、すべてのクエリについての合計で \(\mathrm{O}(N + Q)\) となります。

回答例(C++)