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: {1, 0, 1}
c: {1, 2, 0}
x: {'B', 'C', 'D'}

各マスに、最後に書き換えた操作番号を記録するための二次元配列を用意する。
はじめは、どの操作でも書き換えられていないことを表す -1 で初期化する。
最右列と最下段に無意味なデータを $1$ 列/行だけ置いておくと、あとで累積最大値を取る処理が楽。
（以下の例には記載していない）

vec: {{-1, -1, -1},
      {-1, -1, -1}}

操作 $i$ は、右下のマスが (r[i], c[i]) である長方形を塗り替える。
そのため、いったん vec[r[i]][c[i]] に $i$ を書き込んでおく。

vec: {{-1, -1,  1},
      { 2,  0, -1}}

右下から順に見て、二次元累積最大値を取る。
具体的には、「自身、下のマス、右のマス」の最大値を求めていく。
更新順序の工夫により、各マスには結局、そのマスを含めた右下側にある最大値が入ることになる。

vec: {{ 2,  1,  1},
      { 2,  0, -1}}

答え用の変数 result を、すべて A で初期化する。

result: {"AAA",
         "AAA"}

累積最大値を取った後の vec[i][j] は、マス $(i,j)$ を最後に塗り替える操作番号である。
-1 でなければ、対応する x の値を result[i][j] に書き込む。

マス $(0,0)$ は、vec[0][0] が 2 なので、x[2] を使って D にする。
マス $(0,1)$ は、vec[0][1] が 1 なので、x[1] を使って C にする。
マス $(0,2)$ は、vec[0][2] が 1 なので、x[1] を使って C にする。
マス $(1,0)$ は、vec[1][0] が 2 なので、x[2] を使って D にする。
マス $(1,1)$ は、vec[1][1] が 0 なので、x[0] を使って B にする。
マス $(1,2)$ は、vec[1][2] が -1 なので、A のままでよい。

result: {"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+上書きソート分)$ で解くことができる。
画面上部にあるリンク先の別解コードでは、左上の入力が来ないので、代わりに定数として処理している。
本当に左上もクエリで来る問題を解くには、その部分も書き換えること。