Overview

This problem asks us to count the number of pairs of mountains \((i, j)\) of the same color such that there is no mountain strictly higher than both between them.

The key is that by focusing on the “higher mountain” in each pair, we can easily determine whether the condition is met.

Analysis

For each mountain \(i\), let:

• \(L_i\) be the position of the nearest mountain to the left that is strictly higher than mountain \(i\).
• \(R_i\) be the position of the nearest mountain to the right that is strictly higher than mountain \(i\).

If no such mountain exists, we set \(L_i = 0\) and \(R_i = N+1\), respectively.

In this case, there is no mountain higher than mountain \(i\) within the open interval \((L_i, R_i)\).

---

Let’s consider a pair of the same color \((a, b)\).

Suppose \(H_a > H_b\), meaning mountain \(a\) is higher.

The condition for this pair to have a clear line of sight is:

There is no mountain higher than \(H_a\) between \(a\) and \(b\).

In other words:

Mountain \(b\) lies within the interval \((L_a, R_a)\).

This is because \(L_a\) and \(R_a\) are the nearest mountains strictly higher than mountain \(a\). Any mountain outside this interval would have a mountain higher than mountain \(a\) (and thus higher than both \(a\) and \(b\)) between them.

Therefore, for each mountain \(i\), we just need to count:

The number of mountains of the same color as mountain \(i\) within the interval \((L_i, R_i)\).

However, since this count includes mountain \(i\) itself, we subtract \(1\) at the end.

---

Here, we might worry about double-counting the same pair.

In conclusion, each pair is counted exactly once.

For a pair \((a, b)\) with \(H_a > H_b\), this pair is only counted from the perspective of the higher mountain \(a\).

On the other hand, from the perspective of the lower mountain \(b\), mountain \(a\) itself is a “mountain higher than \(b\)”, so mountain \(a\) lies outside or on the boundary of \((L_b, R_b)\).
Thus, it will not be counted from the lower mountain.

Therefore, we do not need to divide the final answer by \(2\).

---

Naively checking all pairs would take \(O(N^2)\) time.
Since \(N \leq 2 \times 10^5\), this will not run within the time limit.

Instead, we can use the following approach:

1. Use a monotonic stack to find \(L_i\) and \(R_i\) for each mountain.
2. Store the positions of the mountains for each color, and use binary search to count the number of mountains within the interval.

Algorithm

1. Record the positions of each color

For each color \(c\), store the positions of the mountains of that color in pos[c] in ascending order.

Since the input is given from left to right, simply using push_back will keep them in ascending order.

---

2. Find \(L_i\) using a monotonic stack

We iterate from left to right.

We maintain a stack of “mountains that can still be candidates for mountains to their right”, kept in descending order of height.

When considering mountain \(i\), if the top of the stack is lower than mountain \(i\), it cannot be a mountain higher than mountain \(i\), so we pop it.

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

After this process, the mountain at the top of the stack is the nearest higher mountain to the left of mountain \(i\).

If it does not exist, we set \(L_i = 0\).

---

3. Find \(R_i\) in the same way

By performing the same process from right to left, we can find the nearest higher mountain to the right, \(R_i\).

If it does not exist, we set \(R_i = N+1\).

---

4. Count mountains of the same color for each mountain

Let v = pos[C[i]] be the list of positions of the mountains of the same color as mountain \(i\).

We want to find the number of positions \(p\) in v that satisfy:

\[ L_i < p < R_i \]

This can be computed using binary search:

• upper_bound(v.begin(), v.end(), L[i])
  → The first position strictly greater than \(L[i]\).
• lower_bound(v.begin(), v.end(), R[i])
  → The first position greater than or equal to \(R[i]\).

The difference between these two iterators gives the number of mountains of the same color within the interval \((L_i, R_i)\).

Since mountain \(i\) itself is included in this range, we subtract \(1\) and add the result to the total answer.

ans += (it2 - it1) - 1;

Complexity

• Time Complexity: \(O(N \log N)\)
  • Computing \(L_i\) and \(R_i\) using a monotonic stack takes \(O(N)\) time.
  • Performing binary search for each mountain takes \(O(N \log N)\) time in total.
• Space Complexity: \(O(N)\)
  • This is required to store the position lists for each color, \(L_i\), \(R_i\), and the stack.

Key Implementation Points

• The answer can be up to around \(\frac{N(N-1)}{2}\), so use a 64-bit integer type (long long in C++).

• Using \(L_i = 0\) and \(R_i = N+1\) as sentinels makes it easier to handle the interval \((L_i, R_i)\).

• Since elements are added to pos[c] in the order of the input, they are already sorted in ascending order, allowing us to perform binary search directly.

• Since each pair is counted only from the perspective of the higher mountain, there is no need to divide the final answer by \(2\).

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-high.