Overview

This problem asks us to find the number of pairs of mountains (with a clear line of sight) that have the same color, such that all mountains strictly between them are shorter than both of the endpoint mountains, out of \(N\) mountains lined up from east to west.

Analysis

Naive Approach and Its Limitations

If we brute-force all pairs \((i, j)\), there are \(O(N^2)\) pairs. Furthermore, checking the heights of the mountains between each pair takes \(O(N^3)\) time in the worst case, and even if we optimize it to \(O(N^2)\) using prefix sums or segment trees, the complexity remains \(O(N^2)\). Since \(N \le 2 \times 10^5\), this will not run within the time limit (TLE). We need a more efficient approach.

Reformulating the Condition

The condition for a pair \((i, j)\) (\(i < j\)) to have a clear line of sight is: “For all \(k\) (\(i < k < j\)), \(H_k < \max(H_i, H_j)\)” This means “there is no mountain between mountain \(i\) and mountain \(j\) that is higher than \(\max(H_i, H_j)\).”

Here, to organize the relationship regarding the heights of the mountains, we consider a tree structure called a Cartesian Tree. For each mountain \(i\), let \(L_i\) and \(R_i\) be the indices of the first mountains to its left and right, respectively, that are strictly taller than itself. We define the “parent” of mountain \(i\) as the one with the lower height between \(L_i\) and \(R_i\). The tree constructed in this way (a Cartesian Tree based on maximum values) has the following extremely powerful property:

• Vertex \(u\) is a descendant of vertex \(v\) in the tree if and only if the heights of all mountains between mountain \(u\) and mountain \(v\) are strictly less than \(\max(H_u, H_v)\).

Therefore, the condition for a “pair with a clear line of sight” is equivalent to “one vertex is an ancestor (or descendant) of the other in the Cartesian Tree.” Thus, the problem reduces to “counting the number of (ancestor, descendant) pairs with the same color in the Cartesian Tree.”

Algorithm

We can solve the problem with the following steps:

1. Finding the first taller mountains to the left and right (Monotonic Stack) By using a stack, we can find \(L_i\) and \(R_i\) for all \(i\) in \(O(N)\) total time complexity.
2. Constructing the Cartesian Tree For each mountain \(i\), we draw an edge to its parent, which is the one with the lower height between \(L_i\) and \(R_i\). The vertex with no parent (neither \(L_i\) nor \(R_i\) exists) becomes the root of the entire tree (the mountain with the maximum height).
3. Counting pairs using DFS (Depth-First Search) We perform a DFS starting from the root, visiting each vertex in pre-order. During the DFS, we maintain an array color_count representing “how many mountains of each color exist on the path from the root to the current vertex.”
   • Upon reaching vertex \(u\), the value of color_count[C[u]] represents the number of ancestors of vertex \(u\) that have the same color \(C[u]\). We add this value to the answer.
   • Then, we increment color_count[C[u]] by \(1\) and proceed to explore the child nodes.
   • When the search for the subtree of vertex \(u\) is complete and we backtrack (post-order), we decrement color_count[C[u]] by \(1\) to restore its previous state.

To prevent stack overflow due to recursion, it is safer to implement this DFS non-recursively (using an explicit stack), as done in the accepted code.

Complexity

• Time Complexity: \(O(N)\)
  • All steps, including the computation of \(L_i, R_i\), the construction of the Cartesian Tree, and the DFS counting, run in \(O(N)\) time.
• Space Complexity: \(O(N)\)
  • The memory required for the tree’s adjacency list, the stack, and the color count array color_count is \(O(N)\).

Implementation Points

• Avoiding Recursion: In Python, there is a limit on the recursion depth (Recursion Limit). Recursively traversing a tree of size up to \(N = 2 \times 10^5\) may exceed this limit and cause a runtime error. Implementing a non-recursive DFS that manages states (pre-order 0 / post-order 1) with a stack, as in the accepted code, allows for safe and fast processing.

• Using a Monotonic Stack: In the process of finding \(L_i\) and \(R_i\), by utilizing a stack (e.g., by traversing the array in reverse order), even though it might look like a nested loop, each element is pushed to and popped from the stack at most once. Thus, it can be processed in linear time \(O(N)\).

  Source Code

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    
    # C と H を高速に取得
    C = [int(x) for x in input_data[1::2]]
    H = [int(x) for x in input_data[2::2]]
    
    # R_i: i の右側で H が H_i より大きい最初のインデックス
    R = [N] * N
    stack = []
    for i in range(N):
        while stack and H[stack[-1]] < H[i]:
            R[stack.pop()] = i
        stack.append(i)

    # L_i: i の左側で H が H_i より大きい最初のインデックス
    L = [-1] * N
    stack = []
    for i in range(N - 1, -1, -1):
        while stack and H[stack[-1]] < H[i]:
            L[stack.pop()] = i
        stack.append(i)

    # デカルト木の構築
    # 各ノードの親は、L_i と R_i のうち H が小さい方
    children = [[] for _ in range(N)]
    root = -1
    for i in range(N):
        l = L[i]
        r = R[i]
        if l == -1 and r == N:
            root = i
        elif l == -1:
            children[r].append(i)
        elif r == N:
            children[l].append(i)
        else:
            if H[l] < H[r]:
                children[l].append(i)
            else:
                children[r].append(i)

    # 非再帰DFSによる同色祖先ペアのカウント
    color_count = [0] * (N + 1)
    ans = 0
    
    # スタックには (頂点, 状態) を持つ
    # 状態 0: 行きがけ, 1: 帰りがけ
    dfs_stack = [(root, 0)]
    
    while dfs_stack:
        u, state = dfs_stack.pop()
        c = C[u]
        if state == 0:
            ans += color_count[c]
            color_count[c] += 1
            dfs_stack.append((u, 1))
            for v in children[u]:
                dfs_stack.append((v, 0))
        else:
            color_count[c] -= 1

    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.