考察
最後の区間が 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.
出典