概要

各山 \(i\) について「左側に見える山」の個数 \(C_i\) を求め、その総和 \(\sum_{i=1}^{N} C_i\) を高速に計算します。ポイントは「見える山」は左側の“遮られていない高い山”だけであり、単調スタックで一括管理できることです。

考察

山 \(i\) から左を見るとき、山 \(j\,(j<i)\) が見える条件は

• (1) \(H_j > H_i\)（\(i\) より厳密に高い）
• (2) \(j<k<i\) の全てで \(H_k < H_j\)（途中に \(H_j\) 以上が無い）

です。(2) は言い換えると「山 \(j\) は区間 \((j,i)\) の中で一番高い（同じ高さも許さない）」という意味です。

素朴解がなぜダメか

各 \(i\) について左へ走査し、「今までに見つけた最大値」を更新しながら数えることはできますが、最悪で - \(i=1\) は 0 回 - \(i=2\) は 1 回 - … - \(i=N\) は \(N-1\) 回 となり合計 \(O(N^2)\) 回の比較が必要です。\(N \le 10^6\) では到底間に合いません。

重要な気づき

左から右へ順に山を処理するとき、「これから先の山から見える可能性のある山」だけを残しておけばよいです。

• ある新しい山の高さを \(h\) とします。
• 左側に \(h\) 以下の山が残っていても、それらは(1)の \(H_j > H_i\) を満たせない（少なくともこの \(h\) からは見えない）。
• さらに、将来もっと右の山から見ても、間にこの高さ \(h\) の山が入るため、\(h\) 以下の山は 遮られて見えなくなる（条件2で弾かれる）。

よって「スタックの末尾にある \(h\) 以下の高さ」はまとめて捨ててよい、となります。

アルゴリズム

単調減少スタック（strict）を使います。左から右へ山を処理し、スタックには「高さが strictly に減少するように」山の高さだけを積みます。

山の高さを順に \(h=H_i\) として処理します：

1. スタックの末尾が \(h\) 以下の間、末尾を pop する
   
   • while stack and stack[-1] <= h: stack.pop()
   • ここで <= とするのが重要です（同じ高さは条件1で見えない上、条件2でも“以上”が遮るため、同じ高さは残すと不正になります）。
2. pop 後のスタックに残っている要素はすべて \(> h\) で、かつスタックは単調減少
   
   • このとき、スタックに残っている各山は現在の山から見えます。
   • 理由：スタックに残る山より高い（または同じ）山がその右側（現在との間）に存在していたら、その時点で pop されて消えているため、遮るものがありません。
3. よって \(C_i = \text{len(stack)}\) を加算する
   
   • ans += len(stack)
4. 現在の山 \(h\) をスタックに push する
   
   • stack.append(h)

簡単な例

\(H=[5,3,4,2]\) を処理すると：

• \(5\): stack=[] → ans+=0, push 5 → [5]
• \(3\): pop なし → ans+=1（5が見える）, push 3 → [5,3]
• \(4\): 3 は <=4 なので pop → [5] → ans+=1（5が見える）, push 4 → [5,4]
• \(2\): pop なし → ans+=2（5と4が見える）, push 2 → [5,4,2]

総和は \(0+1+1+2=4\)。

計算量

• 時間計算量: \(O(N)\)
  各要素はスタックに 1 回 push され、最大 1 回 pop されるため、全体で線形です。
• 空間計算量: \(O(N)\)
  最悪で単調減少列のときスタックに \(N\) 個積まれます。

実装のポイント

• <= で pop すること：
  同じ高さは「見えない」かつ「遮る」ので、スタックを strict な減少に保つ必要があります。

• \(N=10^6\) のため入出力がボトルネックになりやすいです。提示コードでは sys.stdin.buffer.read() でまとめ読みし、高速に整数をパースしています。

• ans は最大で \(O(N^2)\) 近く（単調減少なら \(\sum_{i=1}^N (i-1)\)）になるため、64bit を超える可能性がありますが、Python の整数は任意精度なのでそのままで問題ありません。

  ソースコード

import sys


def ints():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        x = 0
        while i < n and data[i] > 32:
            x = x * 10 + (data[i] - 48)
            i += 1
        yield x


it = ints()
N = next(it)

stack = []
ans = 0

for _ in range(N):
    h = next(it)
    while stack and stack[-1] <= h:
        stack.pop()
    ans += len(stack)
    stack.append(h)

sys.stdout.write(str(ans))

---

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