Summary

For a pair of mountains \((i, j)\) with the same color, they have a “clear view” of each other if the highest mountain in the interval \([i, j]\) is either of the endpoints, \(i\) or \(j\).
By rephrasing this property using a maximum Cartesian Tree, we can efficiently count the number of pairs that satisfy the condition.

Analysis

First, let us consider the condition for a pair of mountains \(i\) and \(j\) to have a clear view.

The condition is:

\[ H_k \leq \max(H_i, H_j) \text{ for all } k \ (i < k < j) \]

In other words,

the highest mountain in the interval \([i, j]\) is one of the endpoints, \(i\) or \(j\).

If the maximum value in the interval \([i, j]\) is at an intermediate mountain \(k\), then \(H_k\) is higher than both endpoints, so this pair does not have a clear view.

---

This is where we can use a maximum Cartesian Tree.

A maximum Cartesian Tree is a binary tree with the following properties:

• Each mountain is represented by a single vertex.
• An in-order traversal of the tree yields the original sequence of mountains \(1, 2, \dots, N\).
• The elevation of a parent is higher than the elevation of its children.

This tree has an important property:

For any two mountains \(i\) and \(j\), the highest mountain in the interval \([i, j]\) is their Lowest Common Ancestor (LCA) in the Cartesian Tree.

Therefore, the condition for the pair \((i, j)\) to have a clear view is equivalent to:

the LCA of \(i\) and \(j\) is either \(i\) or \(j\).

This is further equivalent to:

one of \(i\) or \(j\) is an ancestor of the other.

In other words, the problem can be rephrased as follows:

Count the number of vertex pairs in the maximum Cartesian Tree that have an ancestor-descendant relationship and share the same color.

---

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

Therefore, we can solve the entire problem in \(O(N)\) time by:

1. Constructing the maximum Cartesian Tree in \(O(N)\) time.
2. Performing a DFS while keeping track of how many ancestors of the current vertex have the same color.

Algorithm

1. Constructing the Maximum Cartesian Tree

We construct a Cartesian Tree where the vertices with larger elevations become parents.

This can be constructed in \(O(N)\) time using a monotonic stack.

The stack maintains the vertices along the rightmost path of the current subtree, sorted by elevation in descending order.

We process the mountains \(i\) from left to right:

• While \(H_i\) is higher than the top of the stack, pop from the stack.
• The last popped vertex becomes the left child of \(i\).
• If there are still vertices left in the stack, \(i\) becomes the right child of the vertex at the top of the stack.
• Push \(i\) onto the stack.

Since each vertex is pushed and popped at most once, the tree construction takes \(O(N)\) time.

---

2. Counting Ancestors of the Same Color using DFS

We perform a DFS on the Cartesian Tree.

During the DFS, we maintain the count of each color along the path from the root to the current vertex in an array cnt[color].

When entering vertex \(v\):

• cnt[C[v]] represents the number of ancestors of \(v\) that have the same color as \(v\).
• All of these ancestors form valid pairs with \(v\).

Therefore, we update the answer:

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

Then, we do:

cnt[C_v] += 1

to search the children, and after the search is complete, we backtrack by doing:

cnt[C_v] -= 1

This ensures that each ancestor-descendant pair is counted exactly once, at the moment the descendant vertex is visited.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Constructing the Cartesian Tree takes \(O(N)\) time, and the DFS visits each vertex exactly once, making the overall complexity \(O(N)\).

Implementation Points

• In Python, recursive DFS can lead to a recursion depth of \(N\), so it is recommended to use an iterative DFS with a stack.

• cnt[c] represents the count of color \(c\) currently on the DFS path.

• Since the maximum answer can be around \(\frac{N(N-1)}{2}\), you must use 64-bit integers in languages like C++.

• Since all elevations \(H_i\) are distinct, the comparison during Cartesian Tree construction only needs to be H[st[-1]] < H[i].

  Source Code

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()

---

This editorial was generated by gpt-5.5-high.