考察
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 #.
出典