Overview

When viewing a mountain range from the west side, the problem asks to determine the number of “visible” mountains within a specified interval for each query. We precompute the transition to the next visible mountain using a monotonic stack, then use doubling (binary lifting) to answer each query efficiently.

Analysis

Rephrasing the “Visible” Condition

Mountain \(k\) is visible in the interval \([L, R]\) means that there is no \(m\) with \(L \le m < k\) such that \(H_m > H_k\). In other words, \(H_k \ge \max(H_L, H_{L+1}, \ldots, H_k)\) holds.

Visible Mountains Form a Chain Structure

Starting from position \(L\) and following the visible mountains in order, we notice that we transition to the next mountain with height greater than or equal to the current mountain.

For example, with \(H = [3, 1, 4, 2, 5]\) starting from \(L=0\): - Mountain 0 (height 3) → The next mountain with height ≥ 3 is mountain 2 (height 4) - Mountain 2 (height 4) → The next mountain with height ≥ 4 is mountain 4 (height 5)

The visible mountains are {0, 2, 4}, totaling 3.

Problem with the Naive Approach

If we scan the interval from left to right for each query, each query takes \(O(N)\) in the worst case, resulting in \(O(NQ)\) overall, which causes TLE.

Solution: Transition Function + Doubling

For each position \(i\), define \(\text{nxt}[i]\) as “the smallest \(j\) to the right of \(i\) satisfying \(H[j] \ge H[i]\)”. Then, the sequence of visible mountains can be traced as \(L \to \text{nxt}[L] \to \text{nxt}[\text{nxt}[L]] \to \cdots\).

By applying doubling to this transition, we can process each query in \(O(\log N)\).

Algorithm

1. Computing \(\text{nxt}[i]\) (Monotonic Stack)
   Scan the array from left to right, maintaining unresolved indices on the stack. If \(H[i]\) is greater than or equal to the value at the top of the stack, set \(\text{nxt}\) of the stack top to \(i\) and pop. This computes everything in \(O(N)\) overall.

2. Building the Doubling Table
   \(\text{up}[k][i]\): the position reached from position \(i\) after \(2^k\) transitions.

   • \(\text{up}[0][i] = \text{nxt}[i]\)
   • \(\text{up}[k][i] = \text{up}[k-1][\text{up}[k-1][i]]\) (if reachable)

3. Answering Queries
   For query \((L, R)\), start with \(\text{cur} = L\), \(\text{count} = 1\). Try \(k\) from largest to smallest; if \(\text{up}[k][\text{cur}] \le R\), jump \(2^k\) steps and add that to count. The final count is the answer.

Complexity

• Time complexity: \(O(N \log N + Q \log N)\) (\(O(N \log N)\) for building the doubling table, \(O(\log N)\) per query)
• Space complexity: \(O(N \log N)\) (doubling table)

Implementation Notes

• Be careful with the definition of \(\text{nxt}\): Transition using “\(H[j] \ge H[i]\)” (greater than or equal). Including equality is necessary because mountains of the same height are also visible.

• Boundary values: Set \(\text{nxt}[i] = N\) (out of array bounds) as default, and in the doubling table, do not transition if the value is \(N\) or greater.

• Conversion to 0-indexed: Since the input is 1-indexed, the internal processing converts to 0-indexed.

• Setting LOG: \(\lceil \log_2(N+1) \rceil + 1\) is sufficient. Since the maximum number of jumps is \(N-1\), \(\log_2 N\) levels are enough to cover it.

  Source Code

import sys
from math import log2, ceil

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    H = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    queries = []
    for j in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        queries.append((L - 1, R - 1, j))  # 0-indexed
    
    # For each query [L, R], count the number of "visible" mountains from the left.
    # A mountain k is visible if no mountain m with L <= m < k has H[m] > H[k].
    # Equivalently, mountain k is visible if H[k] >= max(H[L..k]).
    # This equals the number of "left-to-right maxima (non-strict)" in the subarray.
    
    # We use an offline approach with a stack-based structure.
    # 
    # Key idea: Process queries offline sorted by L (right to left).
    # We maintain a structure where for each position, we know whether it contributes
    # to visibility given a certain starting point.
    #
    # Alternative: Use a merge sort tree / persistent segment tree approach.
    #
    # Approach: Offline with sweepline from right to left on L.
    # For a fixed L, a position k in [L, R] is visible iff H[k] >= max(H[L..k]).
    # As L decreases, the set of visible positions changes.
    #
    # Let's use a different approach: sparse table for range max, and binary lifting
    # to count visible mountains.
    #
    # For each position i, define nxt[i] = the next position j > i such that H[j] >= H[i]
    # (using a monotone stack). Then from L, the visible mountains are L, nxt[L], nxt[nxt[L]], ...
    # until we exceed R. We can use binary lifting on the "nxt" function.
    
    # Compute nxt[i]: next index j > i with H[j] >= H[i]
    nxt = [N] * N  # default: beyond array
    stack = []
    for i in range(N):
        while stack and H[stack[-1]] <= H[i]:
            nxt[stack.pop()] = i
        stack.append(i)
    
    # Binary lifting on nxt
    LOG = max(1, ceil(log2(N + 1)) + 1)
    # up[k][i] = position reached after 2^k jumps from i
    # cnt is implicit: 2^k jumps means 2^k visible mountains after i
    
    up = [[0] * N for _ in range(LOG)]
    up[0] = nxt[:]
    
    for k in range(1, LOG):
        for i in range(N):
            if up[k-1][i] < N:
                up[k][i] = up[k-1][up[k-1][i]]
            else:
                up[k][i] = N
    
    # For query (L, R): start at L (which is always visible, count=1),
    # then jump via nxt. Count how many jumps land within [L, R].
    # The answer = 1 + number of jumps from L that land in <= R.
    
    ans = [0] * Q
    for L, R, j in queries:
        count = 1  # L itself is visible
        cur = L
        for k in range(LOG - 1, -1, -1):
            if up[k][cur] <= R:
                count += (1 << k)
                cur = up[k][cur]
        ans[j] = count
    
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.