ABC 346 E — Paint

考察

各cellの最終色は、そのrowまたはcolumnに対して最後に行われたpaintだけで決まる。operationを逆順に見ると、まだ確定していないcellだけを初めて出会うrow/column操作で一括確定できる。

採用する候補: operationを逆走査し、未処理row/column数から色countを加える

棄却する候補: operationを順にgridへ直接塗る

一回O(H)またはO(W)で、最大4×10^10 cell更新になる。

rowUsed・colUsedをfalse、fixedRows=fixedCols=0としてM-1から0へ走査する。未使用rowならcount[X]+=W-fixedColsとしてmark・fixedRows++、未使用columnならcount[X]+=H-fixedRowsとしてmark・fixedCols++する。残る(H-fixedRows)(W-fixedCols)をcolor0へ加え、正countだけ色昇順に出す。

典型の発動条件

last-write-winsの逆走査

発動条件: 上書き更新列の最終結果だけが必要である。

時系列を逆に辿り、各対象への最初の未確定部分だけを確定する。

未処理dimension数の積

発動条件: row/column全体操作の交差cellを個別に見ず、新規確定数を数えたい。

既確定の反対軸本数を引き、残る列数または行数を寄与にする。

問題固有の要素

同じrowへの古いoperationは、逆走査でrowが既使用なら全cellがより新しいrow/column操作により既に確定しているため完全に無視できる。

別の問題へ持ち帰る視点: 上書き矩形処理は逆順のcovered判定で冗長な過去更新を捨てられる。

正当性

逆順で未処理row rをcolor xに確定すると、既に後時刻のcolumn操作で確定した列を除くW-fixedCols個だけがxになる。columnも対称にH-fixedRows個を確定する。 各row/columnを高々一度だけ処理し、grid cellを列挙せずO(H+W+M)で最終頻度を得られる。

実装上の注意

  • X_i=0のpaintも通常色としてcountへ足し、最後の未確定cellも同じcolor0へ合算する。0個のcolorは出力しない。

復習の核

  • 同じrowの反復、rowとcolumnの上書き順逆転、全軸が一度も塗られない部分、color0によるpaintを小grid simulationと比較する。

計算量と制約

時間

O(H+W+M log M)、色countの平衡mapでM更新。配列色域ならO(H+W+M)。

空間

O(H+W+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq H, W, M \leq 2 \times 10^5; T_i \in \lbrace 1, 2 \rbrace; 1 \leq A_i \leq H for each i such that T_i = 1,; 1 \leq A_i \leq W for each i such that T_i = 2.; 0 \leq X_i \leq 2 \times 10^5; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Paint の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 時間を逆向きにして未来依存を消す

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 逆向きのオフライン処理

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 時間を逆向きにして未来依存を消す

      • 時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。

      この解説で扱わないこと:

      • 値順eventを前から処理するsweep、時刻を反転せずに行う通常のonline更新、および答えの局所寄与だけを集計する順序交換。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題