パナソニックプログラミングコンテスト F - Rook on Grid (600)
基本的にはあるマスの左と上に石がある場合、そのマスには到達できない
$ (1,i)についてはそれより左、$ (i,1)についてはそれより上に石がある場合にそのマス自身にも石があると見做す
全てのマスで左と上の石があるかを調べると$ O(HW(H+W)でTLEする
全ての行で一番左の石を、全ての列で一番上の石の座標を記録する
その座標の左と上の両方に石があるならそのマス自身に石があってもなくても関係ない
石がない場合にはそれぞれ$ H+1行目、$ W+1行目に石があるということにする
行数分の幅のセグ木を持っておく
全ての行を石が右の方にある行から見ていく
前に見た列から今の石がある列までの間の列の一番上の石の座標をセグ木に追加する
セグ木から今見ている石以上の位置にある石の数を求めて答えに追加する
今の行より下の石では到達不可能にはならないため
全ての行列の積から上で求めた到達不可能な点の数を引いたのが答え
範囲内の石の数を求めるところと石の位置でのソートが$ O(H \log H)、石の位置の追加が$ O(W \log H)で全体で$ O((H+W) \log H)