ABC 282 Ex — Min + Sum

考察

B_i≥0なのでprefix sum PBは非減少で、区間minimumが固定されればsumB≤S-minという条件の相手endpoint範囲を二分探索できる。

区間[L,R]のA最小位置Mを選ぶと、Mを含む全subarrayのminimumはA_Mに固定され、残りは左右再帰へ重複なく分割できる。

採用する候補: range minimum位置でdivide-and-conquerし、Mを含むintervalは短い側のendpointだけ列挙して、長い側の有効範囲をPB上のbinary searchで数える。

minimumの変化を消し、各indexの列挙回数をsmall-side規則で対数回に抑えられる。

棄却する候補: 全(l,r)を列挙し、RMQとprefix sumで条件を定数/対数時間判定する。

interval自体が二次個あるためN≤2×10^5に間に合わない。

l≤M≤rなら条件はPB[r]-PB[l-1]≤S-A_Mとなり、l固定ではrのvalid集合がprefix、r固定ではlのvalid集合がsuffixになる。

[L,M]と[M,R]の短い方だけendpointを固定すると、再帰treeで各indexが短い側に入るたび担当区間sizeが少なくとも半減する。

最小位置で左右へ再帰すれば、各subarrayはその最小要素を代表とするnodeで一度だけcross intervalとして数えられる。

RMQまたはmin Cartesian treeで各区間の最小位置Mを得る。leftが短ければ各l∈[L,M]についてPB上で最大r∈[M,R]を探し、rightが短ければ各rについて最小lを探す。cross数を加え、[L,M-1],[M+1,R]へ再帰する。

典型の発動条件

minimum-pivot divide-and-conquer

発動条件: subarray costにminimum/maximumが含まれ、そのextremum位置を含む区間で値を固定できるとき。

range最小位置をpivotにcross intervalを数え、左右へ再帰する。

smaller-side enumeration

発動条件: divide-and-conquerのpivotが偏り得るが、cross pairの片側endpointだけ列挙できるとき。

短い側を走査して各要素の担当回数を対数に抑える。

発動条件: 非負列の区間和上限からendpointの境界を求めるとき。

非減少PBにlower/upper_boundしてvalid endpoint数を取る。

問題固有の要素

minimum pivotを含むintervalではmin項が定数A_Mになり、min+sumという混合条件が単なるprefix sum差の閾値へ変わる。

別の問題へ持ち帰る視点: extremumと加法量が混ざる区間条件では、extremumを固定する分割とprefix sum queryを組み合わせる。

正当性

各区間を最小位置で分けると、その位置を含む区間は現在節点、含まない区間は片側の子に一意に属する。Bの非負性から累積和は非減少なので、一端を固定すれば二分探索で条件を満たす他端の範囲を漏れなく数えられる。短い側を列挙しても各交差区間を落とさない。

実装上の注意

  • S-A_M<0ならpivotを含むgood intervalは0で、unsigned underflowを避ける。
  • B_i=0でPBが同値になるため、≤条件に合うupper_bound/lower_boundの種類と検索区間を正しく選ぶ。

復習の核

  • 同じminimumが複数ある列でtie規約を固定し、あるsubarrayがどのpivot nodeで一度だけ数えられるかCartesian tree上で確認する。

計算量と制約

時間

O(N log²N)、短い側endpointは各要素O(log N)回、各二分探索O(log N)。

空間

O(N)、prefix・Cartesian tree・再帰stack。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 0 \leq S \leq 3 \times 10^{14}; 0 \leq A_i \leq 10^{14}; 0 \leq B_i \leq 10^9; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Min + Sum の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 再帰分割・分割統治

主題
  • 再帰分割・分割統治: pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。
追加で学ぶ技能
    なし
    既習技能
    • 冪等演算のoverlap range query・Sparse Table: 冪等な演算なら重なりを許す二つの2冪区間で任意rangeを覆えることを使い、静的queryをO(1)で答える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。

    主タグ: 再帰分割・分割統治

    補助タグ: 単調進行による償却解析 冪等演算のoverlap range query・Sparse Table

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

    学習の位置

    体系上の位置: 再帰分割・分割統治

    • pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。

    先に読む単元:

    • 単調進行による償却解析 — 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 冪等演算のoverlap range query・Sparse Table — 区間monoid要約で得た考え方と実装を再利用し、冪等演算のoverlap range query・Sparse Tableの発動条件・正当化・境界を重複なく学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題