概要

同じ色の山のペア \((i, j)\) について、区間 \([i, j]\) の中で最も高い山が端点 \(i\) または \(j\) なら「見通しが良い」です。
この性質を 最大 Cartesian Tree に言い換えることで、条件を満たすペア数を効率よく数えます。

考察

まず、山 \(i, j\) のペアが見通しが良い条件を考えます。

条件は、

\[ すべての k \ (i < k < j) について H_k \leq \max(H_i, H_j) \]

です。

これは言い換えると、

区間 \([i, j]\) の中で最も高い山が、端点 \(i\) または \(j\) である

ということです。

もし区間 \([i, j]\) の最大値が途中の山 \(k\) にあるなら、\(H_k\) は両端の山より高いので、このペアは見通しが悪くなります。

---

ここで使うのが 最大 Cartesian Tree です。

最大 Cartesian Tree とは、次の性質を持つ二分木です。

• 各山を 1 つの頂点とする
• 中順巡回すると、山の並び順 \(1, 2, \dots, N\) になる
• 親の標高は子の標高より高い

この木には重要な性質があります。

2 つの山 \(i, j\) に対して、区間 \([i, j]\) で最も高い山は、Cartesian Tree 上での \(i, j\) の LCA、つまり最小共通祖先になる。

したがって、ペア \((i, j)\) が見通しが良い条件は、

\(i, j\) の LCA が \(i\) または \(j\) である

ことと同じです。

これはさらに、

\(i\) と \(j\) のどちらか一方が、もう一方の祖先である

ことと同じです。

つまり、問題は次のように言い換えられます。

最大 Cartesian Tree 上で、祖先と子孫の関係にある頂点ペアのうち、色が同じものの個数を数える。

---

素朴にすべてのペアを調べると \(O(N^2)\) かかります。
\(N \leq 2 \times 10^5\) なので、これは間に合いません。

そこで、

1. 最大 Cartesian Tree を \(O(N)\) で構築する
2. DFS しながら、現在の頂点の祖先に同じ色が何個あるかを数える

ことで、全体を \(O(N)\) で解きます。

アルゴリズム

1. 最大 Cartesian Tree を作る

標高が大きいものが親になる Cartesian Tree を作ります。

これは単調スタックを使うと \(O(N)\) で構築できます。

スタックには、現在見ている部分木の右端方向の頂点を、標高が高い順に保持します。

山 \(i\) を左から順に見ていきます。

• スタックの先頭より \(H_i\) の方が高い間、スタックから取り出す
• 最後に取り出した頂点は、\(i\) の左の子になる
• まだスタックに頂点が残っていれば、\(i\) はその頂点の右の子になる
• \(i\) をスタックに積む

これにより、各頂点は高々 1 回 push / pop されるので、木の構築は \(O(N)\) です。

---

2. DFS で同じ色の祖先を数える

Cartesian Tree 上で DFS します。

DFS 中、現在の根からその頂点までのパス上にある色の個数を cnt[color] として管理します。

頂点 \(v\) に入ったとき、

• cnt[C[v]] は、\(v\) の祖先のうち \(v\) と同じ色の頂点数
• それらすべてと \(v\) は条件を満たすペア

なので、

\[ ans \mathrel{+}= cnt[C_v] \]

とします。

その後、

cnt[C_v] += 1

として子を探索し、探索が終わったら

cnt[C_v] -= 1

として元に戻します。

これにより、各祖先・子孫ペアは子孫側の頂点を訪れたタイミングでちょうど 1 回だけ数えられます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

Cartesian Tree の構築で \(O(N)\)、DFS でも各頂点を 1 回ずつ見るだけなので、全体で \(O(N)\) です。

実装のポイント

• Python では再帰 DFS にすると深さが \(N\) になる可能性があるため、スタックを使った反復 DFS にしています。

• cnt[c] は現在の DFS パス上にある色 \(c\) の個数を表します。

• 答えは最大で \(\frac{N(N-1)}{2}\) 程度になるため、C++ などでは 64 bit 整数を使う必要があります。

• 標高 \(H_i\) はすべて異なるので、Cartesian Tree 構築時の比較は H[st[-1]] < H[i] だけで問題ありません。

  ソースコード

import sys

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

    C = [0] * N
    H = [0] * N
    p = 1
    for i in range(N):
        C[i] = data[p]
        H[i] = data[p + 1]
        p += 2

    left = [-1] * N
    right = [-1] * N
    st = []

    for i in range(N):
        last = -1
        hi = H[i]
        while st and H[st[-1]] < hi:
            last = st.pop()

        if st:
            right[st[-1]] = i
        if last != -1:
            left[i] = last

        st.append(i)

    root = st[0]

    cnt = [0] * (N + 1)
    ans = 0
    stack = [root]

    while stack:
        v = stack.pop()
        if v >= 0:
            c = C[v]
            ans += cnt[c]
            cnt[c] += 1

            stack.append(~v)
            r = right[v]
            l = left[v]
            if r != -1:
                stack.append(r)
            if l != -1:
                stack.append(l)
        else:
            v = ~v
            cnt[C[v]] -= 1

    print(ans)

if __name__ == "__main__":
    main()

---

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