考察
操作iでX_iを書く代わりにtimestamp iを書くと、最終cell(r,c)は r≤R_i,c≤C_i を満たす最大iの値になる。これは各点から右下領域にあるmark最大値を問う二次元suffix maximumである。
採用する候補: 各操作点(R_i,C_i)に最大timestamp iを置き、右下から左上へ grid DPして各cellに max(self,down,right) を伝播し、得たtimestampをX_iへ戻す。
棄却する候補: Q回のrectangle overwriteごとに含まれる全cellを書き換える。
一操作がHW cellsへ及び得て O(HWQ) となる。
H×W配列markを0で初期化し各query iでmark[R_i][C_i]=iへ更新する。r=H..1,c=W..1の順にdown/right最大を伝え、timestamp0なら初期値、正なら対応X_timestampを各cellへ出力する。
典型の発動条件
上書き時刻への変換
発動条件: 複数range overwrite後の最終状態をofflineで求めたいとき。
値でなく操作index最大を求めて最後に値へ写す。
二次元suffix maximum
発動条件: 各cellから右下rectangle内の最大markを全cellで求めたいとき。
右下からdown/rightのmaxを伝播する。
問題固有の要素
offline overwriteは最新操作indexのrange maximum問題へ変えると、値の大小と時系列を分離できる。
別の問題へ持ち帰る視点: anchored rectangle queryは二次元imosの加算でなく、演算maxのsuffix DPとして同じ走査形を使える。
正当性
同じ(R,C)に複数操作がある場合は最大timestampだけ置けば、それ以前はどのcellでも最終値にならない。 suffix rectangle最大は dp[r][c]=max(mark[r][c],dp[r+1][c],dp[r][c+1]) で重複を気にせず計算できる。 cellを覆う操作点集合はそのcellの右下rectangleで、suffix maximum recurrenceがその集合最大timestampをちょうど集約する。
実装上の注意
- R_i,C_iが覆う向きとsuffix走査方向を逆にしない。同一点markは代入ではなく最大timestampを残す。
復習の核
- 一cellを覆う操作条件を操作点のrectangleとして描き、max recurrenceがその全点を含むことを小gridで確認する。
計算量と制約
時間
O(HW+Q)、timestamp配置と2D suffix max。
空間
O(HW+Q)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \le H, W; H \times W \le 10^6; 1 \le Q \le 2 \times 10^5; 1 \le R_i \le H; 1 \le C_i \le W; X_i is an uppercase English letter.; All input numbers are integers.
出典