概要

同じ色の山の組 \((i, j)\) について、間に両方より高い山が存在しないものの個数を数える問題です。

重要なのは、各ペアについて「高い方の山」に注目すると、条件を簡単に判定できることです。

考察

山 \(i\) より高い山のうち、

• 左側で最も近いものの位置を \(L_i\)
• 右側で最も近いものの位置を \(R_i\)

とします。

存在しない場合はそれぞれ \(L_i = 0\), \(R_i = N+1\) とします。

このとき、区間 \((L_i, R_i)\) の中には、山 \(i\) より高い山が存在しません。

---

同じ色のペア \((a, b)\) を考えます。

例えば \(H_a > H_b\)、つまり山 \(a\) の方が高いとします。

このペアが見通しが良い条件は、

\(a\) と \(b\) の間に、\(H_a\) より高い山が存在しない

ことです。

これは言い換えると、

山 \(b\) が区間 \((L_a, R_a)\) の中にある

ということです。

なぜなら、\(L_a\) と \(R_a\) は「山 \(a\) より高い山で最も近いもの」なので、その外側にある山とは途中に山 \(a\) より高い山が挟まれてしまう可能性があるからです。

したがって、各山 \(i\) について、

区間 \((L_i, R_i)\) にある、山 \(i\) と同じ色の山の数

を数えればよいです。

ただし、この数には山 \(i\) 自身も含まれるため、最後に \(1\) を引きます。

---

ここで「同じペアを 2 回数えてしまわないか」が気になります。

結論として、各ペアはちょうど 1 回だけ数えられます。

ペア \((a, b)\) で \(H_a > H_b\) とすると、このペアは高い方である山 \(a\) 側からだけ数えられます。

一方、低い方の山 \(b\) から見ると、山 \(a\) 自身が「\(b\) より高い山」なので、山 \(a\) は \((L_b, R_b)\) の外、または境界になります。
そのため、低い方からは数えられません。

よって、答えを \(2\) で割る必要はありません。

---

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

そこで、

1. 単調スタックで各山の \(L_i\), \(R_i\) を求める
2. 色ごとに山の位置を管理し、二分探索で区間内の個数を数える

という方法を使います。

アルゴリズム

1. 色ごとの位置を記録する

各色 \(c\) について、その色の山の位置を pos[c] に昇順で格納します。

入力は左から順に与えられるので、単に push_back すれば昇順になります。

---

2. 単調スタックで \(L_i\) を求める

左から右に見ていきます。

スタックには「まだ右側の山に対して候補になりうる山」を、高さが大きい順になるように持ちます。

山 \(i\) を見るとき、スタックの一番上が山 \(i\) より低ければ、その山は山 \(i\) より高い山ではないので取り除きます。

while (!st.empty() && H[st.back()] < H[i]) st.pop_back();

この処理後、スタックの一番上にある山が、山 \(i\) の左側で最も近い高い山です。

存在しなければ \(L_i = 0\) とします。

---

3. 同様に \(R_i\) を求める

右から左に同じ処理を行うことで、右側で最も近い高い山 \(R_i\) を求めます。

存在しなければ \(R_i = N+1\) とします。

---

4. 各山について同じ色の山を数える

山 \(i\) と同じ色の山の位置リストを v = pos[C[i]] とします。

求めたいのは、

\[ L_i < p < R_i \]

を満たす位置 \(p\) の個数です。

これは二分探索で求められます。

• upper_bound(v.begin(), v.end(), L[i])
  → \(L_i\) より大きい最初の位置
• lower_bound(v.begin(), v.end(), R[i])
  → \(R_i\) 以上の最初の位置

この差が、区間 \((L_i, R_i)\) にある同じ色の山の個数です。

ただし山 \(i\) 自身も含まれているので、\(1\) を引いて答えに加えます。

ans += (it2 - it1) - 1;

計算量

• 時間計算量: \(O(N \log N)\)
  • 単調スタックによる \(L_i, R_i\) の計算は \(O(N)\)
  • 各山について二分探索を行うので \(O(N \log N)\)
• 空間計算量: \(O(N)\)
  • 色ごとの位置リスト、\(L_i\), \(R_i\)、スタックを持つため

実装のポイント

• 答えは最大で \(\frac{N(N-1)}{2}\) 程度になるため、long long を使います。

• \(L_i = 0\), \(R_i = N+1\) を番兵として使うと、区間 \((L_i, R_i)\) を扱いやすくなります。

• pos[c] は入力順に位置を追加するだけで昇順になるため、そのまま二分探索できます。

• 各ペアは高い方の山からだけ数えられるので、最後に答えを \(2\) で割る必要はありません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> C(N + 1);
    vector<long long> H(N + 1);
    vector<vector<int>> pos(N + 1);

    for (int i = 1; i <= N; i++) {
        cin >> C[i] >> H[i];
        pos[C[i]].push_back(i);
    }

    vector<int> L(N + 1), R(N + 1);
    vector<int> st;

    for (int i = 1; i <= N; i++) {
        while (!st.empty() && H[st.back()] < H[i]) st.pop_back();
        L[i] = st.empty() ? 0 : st.back();
        st.push_back(i);
    }

    st.clear();

    for (int i = N; i >= 1; i--) {
        while (!st.empty() && H[st.back()] < H[i]) st.pop_back();
        R[i] = st.empty() ? N + 1 : st.back();
        st.push_back(i);
    }

    long long ans = 0;

    for (int i = 1; i <= N; i++) {
        const auto& v = pos[C[i]];
        auto it1 = upper_bound(v.begin(), v.end(), L[i]);
        auto it2 = lower_bound(v.begin(), v.end(), R[i]);
        ans += (it2 - it1) - 1;
    }

    cout << ans << '\n';

    return 0;
}

---

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