ABC179 F - Simplified Reversi (600)
縦と横で今何個めくれるのかを全て更新するのは
$ O(Q^2)
かかってしまいTLE
セグ木を使って選ばれた端点だけを更新して保持する
ある列を選んだときにひっくり返せる枚数はそれより後ろの列の値の中での最小値になる
その後その最小値に対応する行の値を更新する
行列が逆の場合も同じ
1クエリ毎に
$ O(\log N)
かかるので全体で
$ O(N + Q \log N)
問題:
https://atcoder.jp/contests/abc179/tasks/abc179_f
提出:
https://atcoder.jp/contests/abc179/submissions/16882916
#ABC179
#600pt
#F
#ABC
#AtCoder