概要

各人 \(i\) のボールは「右側で最初に身長が高い人」へ飛ぶので、まずその相手（次に大きい要素）を求め、次に区間最小値 \(\min(H_i,\dots,H_j)\) を高速に計算して総和を求めます。

考察

重要な観察

• \(i\) 番目の人のボールをキャッチするのは
  \(j>i\) かつ \(H_j>H_i\) を満たす最小の \(j\)（右方向の Next Greater Element）です。
• キャッチされたときのコストは区間 \([i, j]\) の最小値 \(\min(H_i,\dots,H_j)\) です（両端含む）。

よって各 \(i\) について 1. キャッチする人 \(j\) を見つける（いなければコスト \(0\)） 2. その区間最小値を足す
という問題になります。

素朴解が厳しい理由

• 各 \(i\) から右へ見て「最初に高い人」を探す：最悪 \(O(N)\)
• 見つかった \(j\) について区間最小を求めるためにさらに走査：最悪 \(O(N)\)

これを全員分やると最悪 \(O(N^2)\) となり、\(N \le 2\times 10^5\) では間に合いません。

解決方針

• 「右側で最初に高い人（NGE）」は 単調スタック で全体 \(O(N)\) で求められます。
• 「区間最小値」は セグメント木（RMQ） で \(O(\log N)\) で求められます。

これにより全体で \(O(N \log N)\) にできます。

アルゴリズム

1. Next Greater Element（キャッチする相手）を単調スタックで求める

左から順に見ていき、スタックには「まだ自分より右に高い人が見つかっていない人」を、身長が 単調減少 になるように積みます。

現在の人の身長を \(h\) とすると、 - スタック上端の人 \(k\) が \(H_k < h\) なら、\(k\) の「右側で最初に高い人」はまさに今の人なので nge[k] = 現在のindex としてスタックから取り除きます。 - これを繰り返し、最後に現在の人をスタックに積みます。

こうして各 \(i\) について nge[i]（該当がなければ -1）が得られます。
※「厳密に高い」なので比較は \(<\) を使います（同じ身長はキャッチ条件を満たさない）。

2. セグメント木で区間最小値 \(\min(H_i,\dots,H_j)\) を求める

nge[i]=j が求まったら、コストは区間 \([i, j]\) の最小値です。
これを高速に計算するため、配列 \(H\) の 区間最小 を返すセグメント木を構築します。

• 葉に \(H\) を入れ、内部ノードは左右の最小値を保持します。
• 各 \(i\) について j != -1 のとき、セグメント木で \([i, j]\) の最小値を \(O(\log N)\) で取得して合計に加えます。
• j == -1 のときはコスト \(0\) なので無視します。

（例）\(H = [2, 1, 3]\) のとき
- \(i=0(2)\) の次に高い人は \(j=2(3)\)、区間最小は \(\min(2,1,3)=1\)
- \(i=1(1)\) の次に高い人は \(j=2(3)\)、区間最小は \(\min(1,3)=1\)
- \(i=2(3)\) は右にいないので \(0\)
合計は \(2\) になります。

計算量

• 時間計算量:
  
  • NGE 計算（単調スタック）: \(O(N)\)
    
  • 各 \(i\) の RMQ（セグ木）: \(N\) 回 × \(O(\log N)\) で \(O(N\log N)\)
    合計: \(O(N\log N)\)
• 空間計算量:
  
  • nge, スタック, セグメント木で \(O(N)\)

実装のポイント

• キャッチ条件は「厳密に高い」なので、単調スタックでは H[stack[-1]] < h を使います（<= にしない）。

• コストの最小値は区間 \([i, j]\) の 両端を含む ことに注意します。

• セグメント木のサイズを \(2^k \ge N\) となる最小の \(2^k\) にしておくと実装が簡単です（コードでは size = 1 << (N - 1).bit_length()）。

• Python では大量データのため、sys.stdin.buffer.read() で高速入力し、セグ木配列も array('q') を使って高速化しています。

  ソースコード

import sys
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    H = data[1:]

    nge = [-1] * N
    stack = []
    for idx, h in enumerate(H):
        while stack and H[stack[-1]] < h:
            nge[stack.pop()] = idx
        stack.append(idx)

    size = 1 << (N - 1).bit_length()
    base = size
    INF = 10**18

    seg = array('q', [INF]) * (2 * size)
    seg[base:base + N] = array('q', H)

    for i in range(base - 1, 0, -1):
        a = seg[2 * i]
        b = seg[2 * i + 1]
        seg[i] = a if a < b else b

    total = 0
    for i, j in enumerate(nge):
        if j == -1:
            continue
        l = i + base
        r = j + base
        res = INF
        while l <= r:
            if l & 1:
                v = seg[l]
                if v < res:
                    res = v
                l += 1
            if not (r & 1):
                v = seg[r]
                if v < res:
                    res = v
                r -= 1
            l >>= 1
            r >>= 1
        total += res

    sys.stdout.write(str(total))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。