自己記録用 遅延セグ木で殴るのは分かりやすいがO(N+Q)の方は忘れそうだったので。
問題
まず一番下の行と一番右の列が白で埋まっていて、それ以外では黒が端っこのマスを除いた(N-2)2マスに黒を敷き詰める。
クエリではどこに白を置くかが与えられ、最終的に残る黒の数を答える必要がある。
解法
まず一番上の行(パターン1のクエリ)に白が置かれる場合を考える。
一番上の行に白をおいて、黒が幾つひっくり返るかが確定するタイミングは、x列目であればy(y<=x)行目に白石が置かれるタイミングである。これは一番左の行に対するクエリ(パターン2)でも同様に考えられる。
そのため、パターン1とパターン2それぞれでの最も小さいx_iの値を記録しておく。その値と比較して、i番目のクエリx_iが小さいのであれば今まで最も小さかった値から、現在のx_iまでの値を確定させることが出来る。これはパターン1であればパターン2の最も小さかった値、パターン2であればパターン1の最も小さかった値を元に計算することが出来る。
クエリがこれまでの値より大きいのであれば、既に値が確定しているので再度計算する必要はない。
この最も小さい値に応じての計算がクエリ全体でN、クエリ自体がQ個あることからO(N+Q)で求める事ができる。
