Day 152-Q3 | 部分配列の最小値の総和（モノトニックスタック寄与法）

問題

長さ $N$ の整数配列 $A=(A_1,\dots,A_N)$ が与えられる。$1\le l\le r\le N$ を満たすすべての部分配列 $(A_l,\dots,A_r)$ について、その最小値 $\min(A_l,\dots,A_r)$ を計算し、その総和を $10^9+7$ で割った余りを求めよ。

入力形式

N
A_1 A_2 ... A_N

制約

$1 \le N \le 200000$

$1 \le A_i \le 10^9$

入出力例

入力例1

4
3 1 2 4

出力例1

入力例2

3
2 2 2

出力例2

概念図：重複値[2,2,2]での境界と寄与

ヒント（段階的開示）

ヒント1（方向性）

$O(N^2)$通りの部分配列を全部数え上げるのは$N\le200000$では間に合わない。「和 = 各要素 × その要素が最小値になる部分配列の個数」という寄与の形に変形できないか考える。

ヒント2（アプローチ）

要素$A_i$が最小値になるのは「$A_i$より真に小さい要素が区間に含まれない」とき。左右それぞれ「$A_i$より小さい要素が現れるまでの距離」をモノトニックスタックで$O(N)$求め、掛け合わせる。同じ値が複数あるとき二重カウントしないよう、左右で不等号の向き（厳密／等号込み）を変える必要がある。

ヒント3（誘導）

# PLE[i]: i より左で最初に A[j] < A[i] となる j（無ければ -1）
# NLE[i]: i より右で最初に A[k] <= A[i] となる k（無ければ N）
PLE = [-1] * n
stack = []
for i in range(n):
    while stack and A[stack[-1]] >= A[i]:
        stack.pop()
    PLE[i] = stack[-1] if stack else -1
    stack.append(i)

NLE = [n] * n
stack = []
for i in range(n - 1, -1, -1):
    while stack and A[stack[-1]] > A[i]:
        stack.pop()
    NLE[i] = stack[-1] if stack else n
    stack.append(i)

# 各 i の寄与 = A[i] * (i - PLE[i]) * (NLE[i] - i)

模範解答 (Python)

import sys


def main():
    MOD = 10**9 + 7
    data = sys.stdin.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))

    ple = [-1] * n
    stack = []
    for i in range(n):
        while stack and a[stack[-1]] >= a[i]:
            stack.pop()
        ple[i] = stack[-1] if stack else -1
        stack.append(i)

    nle = [n] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and a[stack[-1]] > a[i]:
            stack.pop()
        nle[i] = stack[-1] if stack else n
        stack.append(i)

    ans = 0
    for i in range(n):
        left = i - ple[i]
        right = nle[i] - i
        ans = (ans + a[i] * left % MOD * right) % MOD

    print(ans)


main()

Step-by-Step 解説

1重複なしの例で手計算
A=[3,1,2,4]の全部分配列の最小値の和は$3+1+1+1+1+1+1+2+2+4=17$。寄与法でも値1の寄与$1\times2\times3=6$を含め検算一致。

2重複がある例で非対称境界の必要性を実測
A=[2,2,2]で左右とも厳密未満を境界にすると合計20（正解12を超える二重カウント）。本問の非対称境界（左は厳密未満のみ境界、右は同値も境界）を使うと寄与は$2,4,6$の合計12で一致。

3なぜ非対称にすると二重カウントが消えるか
同じ値が複数箇所にあるとき「その値を代表する添字」を最も左側の出現位置に一意に決めたい。右側だけ「同値も含めて止める」ことで、同値の最小値が複数含まれる部分配列でも最も左の添字だけが「自分が最小値」と主張できるようにする。

よくあるミス

ミス	原因	正しい書き方
左右とも同じ不等号で境界を決めてしまう	重複要素での二重カウントに気づかない	片方は`>=`で押し出し、もう片方は`>`で押し出すと非対称にする
`PLE`/`NLE`の初期値を$0$や$n-1$にしてしまう	「見つからない場合」の番兵を誤る	見つからない場合は`PLE=-1`、`NLE=n`とする
掛け算の途中でmodを取るタイミングを誤る	言語による整数表現の違いを意識していない	Pythonでは問題にならないが、C++等移植時は都度`% MOD`を挟む
スタックに値そのものを積んでしまう	実装の煩雑化	スタックにはインデックスを積み、値は都度`A[]`で引く
$N=1$等コーナーケースでスタックが空の場合の処理漏れ	境界条件の考慮漏れ	`stack`が空なら`PLE=-1`、`NLE=n`とする分岐を必ず入れる

次のステップ

発展: 「最大値の総和」に変えた場合、境界判定の不等号の向きがどう変わるか導出してみる。
次回予告: 永続AVL木（Persistent AVL Tree）

自己評価

完全理解おおむね理解要復習

Day 152-Q3 — 部分配列の最小値の総和（モノトニックスタック寄与法）

問題