ABC 420 F — kirinuki

考察

bottom rowを固定し、各columnの上向き連続dot数h_jを更新すると、横interval幅wから作れるrectangle数はmin(min h on interval,floor(K/w))である。

各intervalをtie-break付き最小h_iへ一意に担当させると、iから左右へ伸ばせる長さa,bが決まり、幅wのinterval個数は増加・一定・減少する台形状の一次関数g(w)になる。

採用する候補: 各rowのhistogramにCartesian tree/monotonic stackでminimum担当範囲を求め、幅別寄与をfloor(K/w)のprefix sumsでO(1)集計する

g(w)は三つの一次関数区間。

棄却する候補: 全top/bottom row pairについて共通dot列を作り、全horizontal intervalを数える

row pairがO(N^2)、さらにcolumn走査が必要で面積制約NM≤5×10^6でも二乗規模になる。

したがって各部分はαw+βで表せる。

各bottom rowでh_jを更新し、(h_j,j)などの一意順序によるnearest smaller境界からa=i-l+1,b=r-i+1を得る。h_i=0はskipし、gの三rangeをd=K/h_iでも分割して、h_iΣ(αw+β)またはαΣwq_w+βΣq_wを足す。全rowの寄与を64 bitで合計する。

典型の発動条件

histogram reduction

発動条件: all-dot subrectangleをbottom固定の連続高さ配列へ変換するとき。

各columnの連続dot数をrowごとにO(1)更新する。

Cartesian tree/monotonic stack

発動条件: 全subarrayを一意なminimum位置へ割り当てたいとき。

tie-break付きnearest smaller境界から各iがminimumとなる左右extentを得る。

floor値の重み付きprefix sum

発動条件: Σ(αw+β)floor(K/w)を多数rangeで求めたいとき。

floor(K/w)とw倍の二prefix配列を前計算する。

問題固有の要素

area≤Kを高さごとに列挙せず、interval minimum hと幅wのmin(h,K/w)へし、幅の選択multiplicityが一次関数になることまで利用する。

別の問題へ持ち帰る視点: subarray minimum寄与に長さ依存capが掛かる場合、担当範囲の長さ分布をpiecewise polynomial化し、cap列のmoment prefixと掛け合わせる。

正当性

a≤bとすればg(w)=w (1≤w≤a)、a (a<w≤b)、a+b-w (b<w≤a+b-1)。したがって各部分はαw+βで表せる。 q_w=floor(K/w)とwq_w=w floor(K/w)のprefixを用意すれば、threshold d=floor(K/h_i)でsplitしたΣg(w)min(h_i,q_w)を、各一次区間につき定数個のprefix差で求められる。 g(w)は三つの一次関数区間。min(h_i,floor(K/w))はw≤floor(K/h_i)でh_i、それ以降floor(K/w)なので、Σq_wとΣwq_wの前計算で各iを定数時間処理できる。

実装上の注意

  • equal hの担当が重複しないよう左右stackのstrict/non-strict規約を対にする。h=0でK/hを計算せず、幅上限M、dのrange外clamp、答えは64 bitとする。

復習の核

  • 全dot、全#、K=1、同じ高さが連続するhistogram、Kが全area以上の小gridをrectangle全列挙と比較する。

計算量と制約

時間

O(HW+W)、H,Wは盤面の高さと幅。floor(K/w)のprefixを先に構築する。

空間

O(W)、高さ・stack・prefix表。入力保存を含めるならO(HW)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: N, M, and K are integers.; 1 \le N,M \le 5 \times 10^5; 1 \le N \times M \le 5 \times 10^6; 1 \le K \le N \times M; S_i is a string of length M consisting of . and #.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 大小関係をCartesian treeへ変換する

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

    主タグ: Cartesian treeによる区間極値分解

    補助タグ: 単調stack・queueによる支配候補の削除 累積和・差分配列

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

    学習の位置

    体系上の位置: 大小関係をCartesian treeへ変換する

    • 配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。

    先に読む単元:

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

    • 最近傍の大小関係だけを答える単調stack、および木を構成せず冪等演算へ答えるRMQ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題