概要

東西に並んだ \(N\) 個の山から、同じ色であり、かつその間にあるすべての山が両端の山のいずれよりも低いようなペア（見通しが良いペア）の個数を求める問題です。

考察

素直なアプローチとその限界

すべてのペア \((i, j)\) を全探索すると \(O(N^2)\) 通りあります。さらに各ペアについて間にある山の高さを確認すると、最悪で \(O(N^3)\)、累積和やセグメント木等を用いて高速化しても \(O(N^2)\) の計算量がかかります。 \(N \le 2 \times 10^5\) であるため、これでは実行時間制限に間に合いません（TLE）。より効率的なアプローチが必要です。

条件の言い換え

見通しが良いペア \((i, j)\) （\(i < j\)）の条件は、 「すべての \(k\) （\(i < k < j\)）について \(H_k < \max(H_i, H_j)\)」 です。これは、「山 \(i\) と山 \(j\) の間に、\(\max(H_i, H_j)\) より高い山が存在しない」 ということを意味します。

ここで、山の標高に関する関係を整理するために、デカルト木（Cartesian Tree） という木構造を考えます。 各山 \(i\) について、左右にある「自身より標高が高い最初の山」のインデックスをそれぞれ \(L_i, R_i\) とします。 山 \(i\) の「親」を、\(L_i\) と \(R_i\) のうち標高が低い方の山と定義します。 このようにして作られる木（最大値に関するデカルト木）には、以下の非常に強力な性質があります。

• 木の中で頂点 \(u\) が頂点 \(v\) の子孫であるとき、かつそのときに限り、山 \(u\) と山 \(v\) の間にあるすべての山の標高は \(\max(H_u, H_v)\) 未満である。

したがって、問題の条件「見通しが良いペア」は、「デカルト木において、一方が他方の祖先（または子孫）関係にある」 ことと同値になります。 これにより、問題は「デカルト木において、同じ色を持つ（祖先, 子孫）のペアの数を数える」という問題に帰着されます。

アルゴリズム

以下のステップで解くことができます。

1. 左右の「自身より高い最初の山」の探索（単調スタック） スタックを用いることで、すべての \(i\) に対する \(L_i\) と \(R_i\) を全体で \(O(N)\) の時間計算量で求めることができます。
2. デカルト木の構築 各山 \(i\) について、\(L_i\) と \(R_i\) のうち標高が低い方を親として辺を張ります。親が存在しない（\(L_i\) も \(R_i\) も存在しない）頂点が、木全体の根（標高が最大の山）になります。
3. DFS（深さ優先探索）によるペアのカウント 根から始めてDFSを行い、行きがけ順で各頂点を訪問します。 DFSの過程で、「根から現在地までのパス上に、各色の山が何個存在するか」を配列 color_count で管理します。
   • 頂点 \(u\) に到達したとき、color_count[C[u]] の値が「頂点 \(u\) の祖先であって、色が \(C[u]\) と同じものの個数」になります。これを答えに加算します。
   • その後、color_count[C[u]] を \(1\) 増やして、子ノードの探索に進みます。
   • 頂点 \(u\) の部分木の探索がすべて終わって戻る（帰りがけ）ときに、color_count[C[u]] を \(1\) 減らして元に戻します。

このDFSは、再帰によるスタックオーバーフローを防ぐため、正解コードのように非再帰（明示的なスタック）で実装すると安全です。

計算量

• 時間計算量: \(O(N)\)
  • \(L_i, R_i\) の計算、デカルト木の構築、DFSによるカウントのすべてのステップが \(O(N)\) で動作します。
• 空間計算量: \(O(N)\)
  • 木の隣接リスト、スタック、および色のカウント配列 color_count に必要なメモリは \(O(N)\) です。

実装のポイント

• 再帰の回避: Pythonでは再帰関数の呼び出し深さ制限（Recursion Limit）があり、最大 \(N = 2 \times 10^5\) の木を再帰で探索すると、制限に達してランタイムエラーになる可能性があります。正解コードのように、状態（行きがけ 0 / 帰りがけ 1）をスタックで管理する非再帰DFSを実装することで、安全かつ高速に処理できます。

• 単調スタックの利用: \(L_i, R_i\) を求める処理は、配列を逆順に走査するなどしてスタックを活用することで、二重ループに見えても各要素がスタックにプッシュ・ポップされる回数は高々1回ずつであるため、線形時間 \(O(N)\) で処理できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    
    # C と H を高速に取得
    C = [int(x) for x in input_data[1::2]]
    H = [int(x) for x in input_data[2::2]]
    
    # R_i: i の右側で H が H_i より大きい最初のインデックス
    R = [N] * N
    stack = []
    for i in range(N):
        while stack and H[stack[-1]] < H[i]:
            R[stack.pop()] = i
        stack.append(i)

    # L_i: i の左側で H が H_i より大きい最初のインデックス
    L = [-1] * N
    stack = []
    for i in range(N - 1, -1, -1):
        while stack and H[stack[-1]] < H[i]:
            L[stack.pop()] = i
        stack.append(i)

    # デカルト木の構築
    # 各ノードの親は、L_i と R_i のうち H が小さい方
    children = [[] for _ in range(N)]
    root = -1
    for i in range(N):
        l = L[i]
        r = R[i]
        if l == -1 and r == N:
            root = i
        elif l == -1:
            children[r].append(i)
        elif r == N:
            children[l].append(i)
        else:
            if H[l] < H[r]:
                children[l].append(i)
            else:
                children[r].append(i)

    # 非再帰DFSによる同色祖先ペアのカウント
    color_count = [0] * (N + 1)
    ans = 0
    
    # スタックには (頂点, 状態) を持つ
    # 状態 0: 行きがけ, 1: 帰りがけ
    dfs_stack = [(root, 0)]
    
    while dfs_stack:
        u, state = dfs_stack.pop()
        c = C[u]
        if state == 0:
            ans += color_count[c]
            color_count[c] += 1
            dfs_stack.append((u, 1))
            for v in children[u]:
                dfs_stack.append((v, 0))
        else:
            color_count[c] -= 1

    print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。