ABC464 E - Fill-Rect Query
矩形塗り替え
考え方
愚直に解くのは非常に簡単だが、計算量が $O(HWQ)$ かかってしまう。
大量に上書きした後で、さらに別のもので同じ範囲を上書きするのは、どう考えても無駄。
結局のところ、各マス最後に塗られた時刻がわかれば、出力の再現はあとで $O(HW)$ で簡単にできる。
つまり、文字種が $26$ 種類しかないことは忘れて、各マス最後に塗られた時刻を求めればよい。
さて、マス $(i,j)$ が最後に塗られた時刻は、$(i以上,j以上)$ というマスが最後に右下になった時刻である。
ということは、全ての書き換えでとりあえず右下だけ記録しておき、まとめて累積最大値を取ればよい。
右下から左上方向に二次元累積最大値を取ることで、$(i以上,j以上)$ という範囲の最大値が $(i,j)$ に残る。
これで、計算量が $O(HW+Q)$ で全てのマスの文字がわかる。
入力例1での動作
入力を受け取る。
r と c は 0-indexed に直しておく。
h: 2
w: 3
q: 3
(r, c, x): {(1, 1, 'B'), (0, 2, 'C'), (1, 0, 'D')}操作番号を $0,1,2$ とする。
各操作について、塗り替える長方形の右下のマスにだけ、その操作番号を記録する。
どの操作の右下でもないマスは $-1$ としておく。
-1 -1 1
2 0 -1次に、右下から左上へ向かって、「自身・下・右」の最大値を取る。
これにより、各マスには、そのマスを含む長方形を塗った操作のうち最後の操作番号が残る。
2 1 1
2 0 -1操作 $0$ の文字は B、操作 $1$ の文字は C、操作 $2$ の文字は D である。
また、$-1$ のマスは一度も塗り替えられていないので A のままとする。
したがって、最終的な盤面は次のようになる。
DCC
DBA注意点
特になし。
別解
左上もクエリ入力される場合の解き方でもよい。
まず、$2W$ 以上の長さの配列を用意する。
中身は priority_queue<pair<int,int>> で、降順に取り出せるようにする。
pair の中身は、「上書き時刻、それを消すタイミング」とする。
これは、扱いとしては横幅 $W$ に対する遅延segment木のようなものと考える。
つまり、各列用ノードに加え、それらを再帰的に $2$ つずつまとめて扱ったノードも用意する。
ただし prod や apply 用の演算はなく、データの入れ方が類似しているだけである。
これに対し、以下の処理ができるようにしておく。
$1$ つめに、$1$ 回 $O(\log W)$ での、区間最大値候補追加。
これは、遅延セグメント木の apply と同じように、ブロックごとに priority_queue に追加する。
例えば $3$ 列目から $10$ 列目までを更新したい場合は、以下を更新する。
- $3$ 列目のデータ
- $4, 5, 6, 7$ 列目のデータ
- $8, 9$ 列目のデータ
- $10$ 列目のデータ
その瞬間最大値ではなくても後に最大値になるかもしれないので、どんな値でも入れておく。
$2$ つめに、延べ $O(HW+Q\log Q \log W)$ での、期限切れの区間最大値削除。
これは、全 priority_queue について、top の削除予定時刻が現在時刻以前である限り pop すればよい。
top に来ていないものは残ってしまうかもしれないが、後に top に来た時に遅延処理で消される。
$3$ つめに、$1$ 回 $O(\log W)$ での、ある列の現在の状態での最大値取得。
これは、遅延セグメント木の一点更新と同じようにすればよい。
すなわち、上へ登りながら各 priority_queue の top の最大値を見ればよい。
この準備ができたら、上の行から順に見ていく。
各行について、以下の $3$ つを順に行えばよい。
- その行から始まる上書き全てについて、最大値候補追加を行う。
- $W$ 列すべてについて、最大値取得を行い、結果に反映する。
- その行で終わる上書き全てについて、最大値削除を行う。
その行から始まる上書きの探索については、事前に適当な方法を用いて開始行でソートしておけばよい。
これで、$O(HW\log W+Q\log Q\log W+上書きソート分)$ で解くことができる。
画面上部にあるリンク先の別解コードでは、左上の入力が来ないので、代わりに定数として処理している。
本当に左上もクエリで来る問題を解くには、その部分も書き換えること。