概要

\(N\) 個の山が一列に並んでおり、各山から左方向に「見える」山の数の合計を求める問題です。単調スタックを用いて「次に自分以上の高さの山が右側のどこにあるか」を求めることで、効率的に解くことができます。

考察

ペアの数え方を変える

各山 \(i\) から見える山 \(j\) の数 \(C_i\) の合計を求めたいので、「見える」ペア \((j, i)\)（\(j < i\)）の総数を数える問題と捉えます。

ペア \((j, i)\) が「見える」条件を整理すると： - \(H_j > H_i\)（山 \(j\) は山 \(i\) より厳密に高い） - \(j < k < i\) なる全ての \(k\) について \(H_k < H_j\)（間の山は全て \(H_j\) より低い）

この2つを合わせると、\(H_j > \max(H_{j+1}, H_{j+2}, \ldots, H_i)\) と同値です。つまり、\(j\) の右隣から \(i\) までの全ての山が \(H_j\) より厳密に低ければよいのです。

山 \(j\) を起点に考える

固定した山 \(j\) について、条件を満たす \(i\) の範囲はどうなるでしょうか？

\(i = j+1\) から右へ順に見ていくと、\(H_{j+1}, H_{j+2}, \ldots\) が全て \(H_j\) より小さい間はペアが成立します。しかし、初めて \(H_k \geq H_j\) となる山 \(k\) が現れると、\(i = k\) 以降は \(\max(H_{j+1}, \ldots, H_i) \geq H_j\) となり条件を満たしません。

つまり、\(\text{next\_ge}(j)\) を「\(j\) より右で初めて \(H_k \geq H_j\) となるインデックス \(k\)」とすると、山 \(j\) から作れるペア数は：

\[\text{next\_ge}(j) - j - 1\]

具体例：\(H = [5, 3, 2, 4, 1]\) の場合 - \(j=0\)（\(H=5\)）：右に \(5\) 以上の山はない → \(\text{next\_ge}(0) = 5\)、ペア数 \(= 5 - 0 - 1 = 4\) - \(j=1\)（\(H=3\)）：\(H_3 = 4 \geq 3\) → \(\text{next\_ge}(1) = 3\)、ペア数 \(= 3 - 1 - 1 = 1\) - \(j=2\)（\(H=2\)）：\(H_3 = 4 \geq 2\) → \(\text{next\_ge}(2) = 3\)、ペア数 \(= 3 - 2 - 1 = 0\) - \(j=3\)（\(H=4\)）：右に \(4\) 以上の山はない → \(\text{next\_ge}(3) = 5\)、ペア数 \(= 5 - 3 - 1 = 1\) - \(j=4\)（\(H=1\)）：右に山がない → \(\text{next\_ge}(4) = 5\)、ペア数 \(= 5 - 4 - 1 = 0\)

合計 \(= 4 + 1 + 0 + 1 + 0 = 6\)

素朴なアプローチの問題

各 \(j\) に対して右方向に順に走査して \(\text{next\_ge}(j)\) を求めると、最悪 \(O(N^2)\) かかり \(N = 10^6\) では TLE になります。

アルゴリズム

単調スタック を使って全ての \(j\) の \(\text{next\_ge}(j)\) を \(O(N)\) で求めます。

1. スタック（インデックスを格納）を用意する。
2. \(k = 0, 1, \ldots, N-1\) の順に走査する。
3. 各 \(k\) について、スタックの先頭の山 \(j\) が \(H_j \leq H_k\) である限り、\(j\) をポップして \(\text{next\_ge}(j) = k\) と記録する。
4. \(k\) をスタックにプッシュする。
5. 走査終了後、スタックに残った山は右に自分以上の山がないので \(\text{next\_ge}(j) = N\) とする（初期値）。

最後に \(\displaystyle\sum_{j=0}^{N-1} (\text{next\_ge}(j) - j - 1)\) を計算して出力します。

スタックの性質：スタック内の山の標高は常に単調減少に保たれます。\(H_k\) がスタック先頭以上なら先頭をポップするため、小さいものが大きいものに「駆逐」される構造です。各要素はちょうど1回プッシュ・1回ポップされるので全体 \(O(N)\) です。

計算量

• 時間計算量: \(O(N)\)（各要素がスタックに1回ずつ出入りする）
• 空間計算量: \(O(N)\)（配列とスタックの分）

実装のポイント

• \(\text{next\_ge}\) の初期値を \(N\) にする：スタックに残った要素は右端を超えても該当する山がないことを意味し、\(\text{next\_ge}(j) = N\) が正しい値になります。

• ポップ条件は \(H_j \leq H_k\)（等号含む）：「次に 以上 の高さの山」を求めるため、等しい場合もポップします。

• 高速な入力：\(N\) が最大 \(10^6\) なので、sys.stdin.buffer.read() でまとめて読み込むことで入力を高速化しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    H = [int(input_data[i+1]) for i in range(N)]
    
    # For each mountain i, we need to count how many mountains j < i are "visible" from i.
    # Mountain j is visible from i if:
    #   1. H[j] > H[i]
    #   2. For all k with j < k < i, H[k] < H[j]
    
    # Condition 2 means: H[j] is strictly greater than all mountains between j and i.
    # This means H[j] must be strictly greater than the maximum of H[j+1..i-1].
    
    # Key insight: Consider maintaining a stack of "visible candidates" from left to right.
    # The stack maintains mountains in decreasing order of height (monotone stack).
    
    # For each mountain i, the mountains that are visible from i are exactly those
    # mountains j in the stack (when processing i) such that H[j] > H[i].
    
    # Let's think differently. We want sum over all i of C_i.
    # Equivalently, we count the number of pairs (j, i) with j < i such that:
    #   (a) H[j] > H[i]
    #   (b) max(H[j+1..i-1]) < H[j]  (vacuously true if j = i-1)
    
    # Condition (b) means H[j] > H[k] for all j < k < i.
    # Combined: H[j] > max(H[i], max of H[j+1..i-1]) = max(H[j+1..i])... wait no.
    # H[j] > H[k] for all j < k < i, AND H[j] > H[i].
    # So H[j] > max(H[j+1], ..., H[i]).
    
    # So we need to count pairs (j, i) with j < i where H[j] > max(H[j+1..i]).
    
    # For a fixed j, the mountains i > j where H[j] > max(H[j+1..i]) are:
    # i = j+1, j+2, ... up to the first index where H[k] >= H[j] for some k in [j+1..i].
    # Actually, we need max(H[j+1..i]) < H[j].
    # Starting from i = j+1: max = H[j+1]. Valid if H[j+1] < H[j].
    # i = j+2: max = max(H[j+1], H[j+2]). Valid if both < H[j].
    # Continue until we hit some index where H >= H[j].
    
    # So for each j, the count is the number of consecutive elements after j that are all
    # strictly less than H[j], i.e., the distance to the first element >= H[j] to the right.
    
    # This is a classic "next greater or equal element" problem solvable with a monotone stack.
    
    # For each j, let next_ge[j] be the smallest index k > j such that H[k] >= H[j].
    # If no such k exists, next_ge[j] = N.
    # Then the number of valid i for this j is: next_ge[j] - j - 1.
    # Wait: valid i range is j+1 to next_ge[j]-1 (inclusive), 
    # because at next_ge[j], max(H[j+1..next_ge[j]]) >= H[j].
    # Count = next_ge[j] - 1 - (j+1) + 1 = next_ge[j] - j - 1.
    
    # Total answer = sum over j of (next_ge[j] - j - 1).
    
    # Find next_ge using monotone stack (from right to left, or left to right).
    
    next_ge = [N] * N
    stack = []  # stack of indices, maintaining increasing order of index, decreasing won't work simply
    
    # Standard approach: iterate from right to left
    # Actually, let's use left-to-right with a stack storing indices in decreasing H order.
    
    # Left to right: maintain stack. For each new element H[k], pop all stack elements with H < H[k]... 
    # we need next >= , so pop while stack top has H[stack_top] <= H[k]? No.
    # We want next_ge[j] = first k > j with H[k] >= H[j].
    # Use a stack: iterate k from left to right. For each k, pop all j from stack where H[j] <= H[k],
    # and set next_ge[j] = k. Then push k.
    
    stack = []
    for k in range(N):
        while stack and H[stack[-1]] <= H[k]:
            j = stack.pop()
            next_ge[j] = k
        stack.append(k)
    
    ans = 0
    for j in range(N):
        ans += next_ge[j] - j - 1
    
    print(ans)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。