概要

同じ色の山のペアのうち、その間にある山がすべて「両端の山のいずれか以下」であるものの個数を求める問題です。

一見複雑に見える「見通しが良い」という条件を、各山から左右に存在する「自身より高い最初の山」の位置に言い換えることで、単調スタックと二分探索を用いて \(O(N \log N)\) で高速に解くことができます。

---

考察

1. 素朴なアプローチとその限界

すべての同じ色のペア \((i, j)\) （ \(i < j\) ）について、その間にあるすべての山 \(k\) が \(H_k \leq \max(H_i, H_j)\) を満たすか愚直に判定すると、最悪の場合で \(O(N^3)\) や \(O(N^2)\) の時間がかかってしまい、 \(N \le 2 \times 10^5\) という制約下では実行時間制限に間に合いません（TLE）。

より効率的に条件を満たすペアを数え上げる必要があります。

2. 条件の言い換え

問題文の条件「すべての \(k\) （ \(i < k < j\) ）について \(H_k \leq \max(H_i, H_j)\) 」を整理します。 すべての山の標高は異なる（ \(H_i \neq H_j\) ）ため、ペア \((i, j)\) は以下の 2 つのケースに完全に分類できます。

ケース 1: \(H_i > H_j\) の場合

このとき、 \(\max(H_i, H_j) = H_i\) となります。 条件は「 \(i < k < j\) を満たすすべての \(k\) について \(H_k < H_i\) 」となります。

これは、「山 \(i\) より右側にあって、山 \(i\) より高い最初の山」を \(R_i\) としたとき、 \(j < R_i\) であることと同値です。 したがって、以下の条件をすべて満たす \(j\) の個数を数えればよいです。 - \(i < j < R_i\) - \(C_i = C_j\)

ケース 2: \(H_i < H_j\) の場合

このとき、 \(\max(H_i, H_j) = H_j\) となります。 条件は「 \(i < k < j\) を満たすすべての \(k\) について \(H_k < H_j\) 」となります。

これは、「山 \(j\) より左側にあって、山 \(j\) より高い最初の山」を \(L_j\) としたとき、 \(L_j < i\) であることと同値です。 したがって、各 \(j\) を固定したとき、以下の条件をすべて満たす \(i\) の個数を数えればよいです。 - \(L_j < i < j\) - \(C_i = C_j\)

この 2 つのケースは排他的（ \(H_i > H_j\) と \(H_i < H_j\) は同時に起こらない）であるため、それぞれのケースで条件を満たすペアの個数を独立に数え上げて足し合わせることで、重複なくすべての「見通しが良いペア」を網羅できます。

---

アルゴリズム

プログラムは以下の 3 つのステップで動作します。

ステップ 1: 左右の「自身より高い最初の山」の探索（単調スタック）

各山 \(i\) について、以下の値を求めます。 - \(L_i\): \(i\) より左側（ \(k < i\) ）で \(H_k > H_i\) を満たす最大の \(k\) （存在しない場合は \(-1\) ） - \(R_i\): \(i\) より右側（ \(k > i\) ）で \(H_k > H_i\) を満たす最小 \(k\) （存在しない場合は \(N\) ）

これらは、単調スタック（Monotonic Stack）と呼ばれる手法を用いることで、全体で \(O(N)\) の時間計算量で求めることができます。

ステップ 2: 色ごとの山リストの作成

各色 \(c\) について、その色を持つ山のインデックスを昇順に並べたリスト pos[c] を作成します。 また、各山 \(i\) が pos[C[i]] の中で何番目の要素であるかを表すインデックス idx_in_pos[i] も記録しておきます。

ステップ 3: 二分探索による高速な数え上げ

各山 \(i\) について、自身を端点とする有効なペアの数を二分探索（lower_bound / upper_bound）を用いて高速に数え上げます。

• ケース 1 の数え上げ (\(H_i > H_j\)): pos[C[i]] の中で、インデックスが \(i\) より大きく \(R_i\) 未満である要素の個数を求めます。 これは、 pos[C[i]] の中から二分探索で \(R_i\) 以上の最初の要素の位置を特定し、そこから \(i\) 以下の要素の個数（ idx_in_pos[i] + 1 ）を引くことで \(O(\log N)\) で計算できます。

• ケース 2 の数え上げ (\(H_i < H_j\)): 山 \(j\)（コード中ではループ変数 i）を固定し、 pos[C[j]] の中で、インデックスが \(L_j\) より大きく \(j\) 未満である要素の個数を求めます。 これは、 pos[C[j]] の中から二分探索で \(L_j\) より大きい最初の要素の位置を特定し、 \(j\) 自身の位置（ idx_in_pos[j] ）からその位置を引くことで \(O(\log N)\) で計算できます。

---

計算量

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

  • \(L_i, R_i\) の計算に \(O(N)\) かかります。
  • 色ごとのインデックスリストの構築に \(O(N)\) かかります。
  • 各山 \(i\) について、 \(2\) 回の二分探索を全 \(N\) 個の要素に対して行うため、数え上げに \(O(N \log N)\) かかります。
  • したがって、全体の時間計算量は \(O(N \log N)\) となり、実行時間制限に十分間に合います。

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

  • 配列 L, R, pos, idx_in_pos およびスタック st は、いずれも要素数が最大 \(N\)（または \(N+1\)）であるため、空間計算量は \(O(N)\) です。

---

実装のポイント

• 単調スタックの挙動: 左から右へ走査しながら、スタック内の「現在注目している山より低い山」をすべて取り除く（pop する）ことで、スタックの末尾には常に「自身より左側で最も近い、自身より高い山」が残るようになります。右側についても同様に、右から左へ走査することで \(R_i\) を求められます。

• 二分探索の境界値: \(L_i\) や \(R_i\) が存在しない場合の番兵として、 \(L_i\) には \(-1\) を、 \(R_i\) には \(N\) を設定しておくことで、境界条件の処理を簡潔にしています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> C(N);
    vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> C[i] >> H[i];
    }

    // L[i]: i より左側で H[i] より高い最初の要素のインデックス
    // R[i]: i より右側で H[i] より高い最初の要素のインデックス
    vector<int> L(N, -1), R(N, N);
    vector<int> st;
    for (int i = 0; i < N; ++i) {
        while (!st.empty() && H[st.back()] < H[i]) {
            st.pop_back();
        }
        if (!st.empty()) L[i] = st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = N - 1; i >= 0; --i) {
        while (!st.empty() && H[st.back()] < H[i]) {
            st.pop_back();
        }
        if (!st.empty()) R[i] = st.back();
        st.push_back(i);
    }

    // 各色ごとのインデックスのリスト
    vector<vector<int>> pos(N + 1);
    // idx_in_pos[i]: pos[C[i]] における要素 i のインデックス
    vector<int> idx_in_pos(N);
    for (int i = 0; i < N; ++i) {
        idx_in_pos[i] = pos[C[i]].size();
        pos[C[i]].push_back(i);
    }

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        // Case 1: H_i > H_j (i < j < R_i かつ C_i = C_j)
        {
            int limit_r = R[i];
            auto it = lower_bound(pos[C[i]].begin(), pos[C[i]].end(), limit_r);
            int idx_limit = distance(pos[C[i]].begin(), it);
            int idx_cur = idx_in_pos[i];
            if (idx_limit > idx_cur + 1) {
                ans += (idx_limit - (idx_cur + 1));
            }
        }
        // Case 2: H_i < H_j (L_j < i < j かつ C_i = C_j)
        // ここでは j をループの変数 i とみなして計算する
        {
            int limit_l = L[i];
            auto it = upper_bound(pos[C[i]].begin(), pos[C[i]].end(), limit_l);
            int idx_limit = distance(pos[C[i]].begin(), it);
            int idx_cur = idx_in_pos[i];
            if (idx_cur > idx_limit) {
                ans += (idx_cur - idx_limit);
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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