Overview

This problem asks us to efficiently answer queries: given an interval \([L_j, R_j]\), starting from the leftmost mountain and looking rightward in order, how many mountains have a height greater than or equal to the maximum elevation seen so far?

By using doubling (binary lifting) and a monotonic stack, we can answer each query efficiently.

---

Analysis

1. Naive Approach and Its Limitations

The simplest method is, for each query \((L, R)\), to loop from \(L\) to \(R\), updating the maximum elevation seen so far and counting the visible mountains.

However, this method takes \(O(N)\) time in the worst case for a single query. Since there are \(Q\) queries, the total time complexity becomes \(O(NQ)\), which will result in a Time Limit Exceeded (TLE) under the given constraints (\(N, Q \le 2 \times 10^5\)). We need a faster approach, such as \(O(\log N)\) or \(O(1)\) per query.

2. Focusing on Transitions to the “Next Visible Mountain”

Let’s organize the conditions for a mountain to be visible. When mountain \(i\) is visible within the interval, what does the next visible mountain look like?

It is “the first mountain to the right of mountain \(i\) with an elevation greater than or equal to \(H_i\)”. This is because all mountains between mountain \(i\) and the “next mountain with elevation \(\ge H_i\)” have elevations strictly less than \(H_i\), so they are blocked by mountain \(i\) and cannot be seen.

Let’s call the index of the next visible mountain after mountain \(i\) as \(next\_idx[i]\). Then, the visible mountains in the interval \([L, R]\) follow a unique chain of transitions:

\[L \to next\_idx[L] \to next\_idx[next\_idx[L]] \to \cdots\]

The number of visible mountains is “the number of transitions before exceeding the right endpoint \(R\), plus 1 (for the starting mountain \(L\))”.

3. Idea for Speedup (Doubling)

If we follow transitions one by one, we may need up to \(O(N)\) transitions in the worst case, which doesn’t improve performance. However, since “the next transition destination is uniquely determined,” we can apply doubling (binary lifting).

Doubling is a technique that precomputes “the destination after \(1, 2, 4, 8, \ldots\) steps,” allowing us to find the destination after any number of steps in \(O(\log N)\).

---

Algorithm

Specifically, we find the solution in the following 3 steps.

Step 1: Constructing \(next\_idx\) (Monotonic Stack)

For each mountain \(i\), we find the index \(next\_idx[i]\) of the first mountain to the right with elevation \(\ge H_i\). This can be computed in \(O(N)\) overall by scanning the array from right to left while maintaining a stack.

1. Place a sentinel (elevation \(2 \times 10^9\)) beyond the right end (at index \(N+1\)), which is taller than any mountain.
2. Process mountains from right to left.
3. While the mountain at the top of the stack has elevation less than \(H_i\), pop it from the stack.
4. After this operation, the mountain at the top of the stack is “the first mountain to the right of mountain \(i\) with elevation \(\ge H_i\).” Set this as \(next\_idx[i]\).
5. Push mountain \(i\) onto the stack and move to the next mountain on the left.

Step 2: Constructing the Doubling Table

Define \(dp[k][i]\) as “the index of the mountain reached after \(2^k\) transitions starting from mountain \(i\).”

The initial state (\(2^0 = 1\) transition) is exactly \(next\_idx\) computed in Step 1: $\(dp[0][i] = next\_idx[i]\)$

A transition of \(2^{k+1}\) steps can be rephrased as “transitioning \(2^k\) steps from the result of transitioning \(2^k\) steps,” so the table can be filled with the following recurrence: $\(dp[k+1][i] = dp[k][dp[k][i]]\)$

For the range of \(k\), it suffices to compute up to \(K \approx 18\) such that \(2^K \ge N\).

Step 3: Answering Queries

For each query \((L, R)\), we answer as follows:

1. Set the current position to \(curr = L\) and the answer to \(ans = 1\) (counting the leftmost mountain \(L\)).
2. Try steps from largest to smallest: \(k = K-1, K-2, \ldots, 0\).
3. If the destination after \(2^k\) transitions is within \(R\) (\(dp[k][curr] \le R\)), then jump to that destination (\(curr = dp[k][curr]\)) and add \(2^k\) to the answer (\(ans \leftarrow ans + 2^k\)).
4. After repeating this down to \(k=0\), the value of \(ans\) is the number of visible mountains for that query.

---

Complexity

• Time Complexity: \(O((N + Q) \log N)\)
  • Constructing \(next\_idx\): Each element is pushed to and popped from the stack at most once, so this is \(O(N)\).
  • Constructing the doubling table: \(O(N \log N)\).
  • Processing queries: Each query is processed in \(O(\log N)\). For all \(Q\) queries, this is \(O(Q \log N)\).
• Space Complexity: \(O(N \log N)\)
  • The doubling table \(dp\) has size \(K \times (N+2)\), which is the bottleneck for space complexity.

---

Implementation Notes

• Role of the Sentinel: If no mountain to the right has height \(\ge\) the current mountain, the transition destination would go out of bounds. To prevent this, we place a very tall mountain (with elevation \(2 \times 10^9\) or some sufficiently large value) as a sentinel at the end. This allows for a simple implementation without any special-case handling.

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    Q = int(input_data[1])

    H = [0] * (N + 2)
    for i in range(N):
        H[i + 1] = int(input_data[2 + i])
    H[N + 1] = 2000000000

    next_idx = [0] * (N + 2)
    stack = [N + 1]
    for i in range(N, 0, -1):
        h = H[i]
        while H[stack[-1]] < h:
            stack.pop()
        next_idx[i] = stack[-1]
        stack.append(i)
    next_idx[N + 1] = N + 1

    K = 18
    dp = [None] * K
    dp[0] = next_idx
    for k in range(K - 1):
        prev = dp[k]
        dp[k + 1] = [prev[p] for p in prev]

    out = []
    idx = 2 + N
    for _ in range(Q):
        L = int(input_data[idx])
        R = int(input_data[idx + 1])
        idx += 2

        curr = L
        ans = 1
        for k in range(K - 1, -1, -1):
            nxt = dp[k][curr]
            if nxt <= R:
                curr = nxt
                ans += 1 << k
        out.append(str(ans))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

---

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