ABC 234 G — Divide a Sequence

考察

最後の区間が A_{j+1}…A_i である分割の寄与は、prefix j の全分割積 dp_j にその区間の max−min を掛けたものになる。

よって dp_i は全 j の重み付き区間最大値和から重み付き区間最小値和を引いた形であり、両者を独立に維持できる。

棄却する候補: 各右端 i について全ての左端 j を遡り、区間の最大・最小を更新しながら dp_j を加える。

最大・最小の更新は軽くても区間が二乗個あり、N=30 万では処理できない。

採用する候補: 現在右端に対する区間最大値が同じ左端群を単調減少 stack、最小値が同じ群を単調増加 stack にまとめ、群の dp 重み和と寄与総和を更新する。

新しい A_i が極値を更新する連続群を一括併合でき、各左端は各 stack へ一度 push・pop される。

初期値はdp_0=1(空prefixの分割積)、max/minのstackは空、寄与総和U=V=0。i=1,…,Nでa=A_iを読むとき、次を行う。

w=dp_{i−1}
while maxStackが非空でtop.value≤a:
    (v,s)=pop(); U−=v·s; w+=s
push(a,w); U+=a·w

w=dp_{i−1}
while minStackが非空でtop.value≥a:
    (v,s)=pop(); V−=v·s; w+=s
push(a,w); V+=a·w

dp_i=U−V

全加減乗算は法998244353。dp_{i−1}は両stackを更新し終えるまで保持する。popした群の左端は全て新しい極値aを持つので、旧寄与v·sを引き、重みをまとめたa·wへ置き換えられる。新しい一要素区間の重みdp_{i−1}も一緒に入るが、maxとminが同じaなので差は0。N=1ではdp_1=0、A=(1,3)ではdp_2=2となる。答えはdp_N。

典型の発動条件

重み付き区間極値和の単調スタック

発動条件: 全左端から現在右端までの max または min に、左端ごとの重みを掛けた総和を逐次求めるとき。

同じ極値を共有する左端の重み和を stack 要素へまとめ、新値で pop される群の寄与を一括置換する。

最後の区間を固定する分割 DP

発動条件: 列を連続区間へ分け、各区間評価の積または加算を全分割について集約するとき。

最後の切れ目 j を固定し、prefix の集約値 dp_j と最後区間の評価を掛けて足す。

問題固有の要素

区間評価 max−min をそのまま管理せず、max の総和と min の総和へ分けると同じ単調スタック処理を符号違いで二回使える。

別の問題へ持ち帰る視点: 複合した区間統計が線形結合なら、各成分を高速化しやすい標準統計へ分解してから合成する。

正当性

prefix iの分割は最後の切れ目jによって一意に分かれ、dp_i=Σ_{0≤j<i}dp_j(max A[j+1:i]−min A[j+1:i])である。空prefixの重みdp_0=1が最初の区間を数える。各stackは同じ極値を持つ左端群とその重み和を表し、pop・寄与の除去・新値への合併が全左端の新しい極値を保存する。従って更新後U,Vは漸化式の二つの総和で、dp_i=U−Vは全分割積の和になる。

実装上の注意

  • 新しい一要素区間の左端重み dp_{i−1} を max・min 両 stack へ加え、その同じ値の寄与が差で 0 になるようにする。
  • 同値を pop する比較規則を各 stack で統一し、寄与の減算後は法 998244353 の非負範囲へ戻す。

復習の核

  • 最後の区間の全左端を足す DP で max・min が現れたら、右端追加時に極値が同じ左端群を単調 stack でまとめる。
  • stack 要素の意味を「値」だけでなく「その値を担当する dp 重みの総和」として説明できるようにする。

計算量と制約

時間

O(N)、各単調stackへのpush/popは一度ずつ。

空間

O(N)。

制約との対応

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

Divide a Sequence の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 支配関係から不要な候補を単調stack・queueで削る

主題
追加で学ぶ技能
    なし
    既習技能
    • prefix分割DP: 列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 単調stack・queueによる支配候補の削除

    補助タグ: prefix分割DP

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

    学習の位置

    体系上の位置: 支配関係から不要な候補を単調stack・queueで削る

    • 候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。

    先に読む単元:

    • prefix分割DP — DPの最小十分状態で得た考え方と実装を再利用し、prefix分割DPの発動条件・正当化・境界を重複なく学ぶ。

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

    • 全候補から極値を反復取得するheap・ordered set。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題