Overview

For each query interval \([L,R]\), we efficiently compute the number of mountains that “update the maximum elevation so far (including ties) when viewed from the left” (= the number of visible mountains).

Analysis

Rephrasing “Visible”

The condition for mountain \(k\) to be visible is “there is no mountain strictly taller than it to its left.” So when scanning the interval \([L,R]\) from left to right:

• Let \(M\) be the maximum value up to the current point
• Mountain \(k\) is visible only when \(H_k \ge M\) (mountains of the same height are also visible)

In other words, visible mountains correspond to the “prefix maximum sequence of the interval (allowing ties).”

Problem with the Naive Approach

If we scan from \(L\) to \(R\) for each query, updating the maximum and counting, it takes \(O(R-L+1)\). In the worst case this is \(O(NQ)\), which is too slow for \(N,Q \le 2\times 10^5\).

Key Observation: The Maximum is Only Updated by “the Next Taller Mountain”

When at position \(i\) with the current maximum being \(H_i\), the next time the maximum gets updated is when we reach “the first mountain to the right of \(i\) that is strictly taller than \(H_i\).”

So for each \(i\), define:

• \(\mathrm{nge}[i]\) = the first position to the right where \(H_{\mathrm{nge}[i]} > H_i\) (or sentinel \(N+1\) if none exists)

Then within the interval \([i,\,\mathrm{nge}[i)-1]\), the maximum remains \(H_i\).

Within this interval, only “mountains with height exactly \(H_i\)” are visible (mountains shorter than this lose to the maximum and are not visible). Therefore:

• \(w[i]\) = the number of mountains with height \(H_i\) contained in the interval \([i,\,\mathrm{nge}[i)-1]\)

If we know this, a query becomes: - Start at \(i=L\), follow \(\mathrm{nge}\) links, accumulating \(w\) values (though the last segment may be cut short, requiring special handling).

Algorithm

1. Build \(\mathrm{nge}\) (Next Greater Element) Using a Monotone Stack

Scan from right to left, maintaining a stack of candidate mountains in monotonically increasing height order.

• Mountains with height \(\le H_i\) cannot be the “next strictly taller mountain” from \(i\), so pop them
• The remaining top of the stack is \(\mathrm{nge}[i]\) (or \(N+1\) if the stack is empty)

This builds the entire array in \(O(N)\).

2. Compute \(w[i]\) Using “Position Lists by Height”

For each elevation \(h\), maintain an array \(\text{pos}[h]\) of its occurrence positions in ascending order.

For position \(i\) with height \(h=H_i\) and interval endpoint \(end=\mathrm{nge}[i]-1\): - \(w[i]\) = the number of elements in \(\text{pos}[h]\) that fall within \([i,end]\)

This can be found using binary search. In the implementation: - rank[i] = the index of \(i\) within \(\text{pos}[H_i]\) (0-indexed)

Then: - bisect_right(pos[h], end) - rank[i] gives the count in \([i,end]\) in one shot.

3. Speed Up \(\mathrm{nge}\) Jumps with Binary Lifting (Doubling)

Since \(\mathrm{nge}\) is a pointer to the “next taller mountain,” following it repeatedly makes queries slow. So we build a binary lifting table:

• up[k][i] = the position reached after following \(\mathrm{nge}\) \(2^k\) times
• sw[k][i] = the sum of \(w\) values accumulated along that path

The transitions are: - up[k][i] = up[k-1][ up[k-1][i] ] - sw[k][i] = sw[k-1][i] + sw[k-1][ up[k-1][i] ]

4. Query Processing

For a query \([L,R]\), we use binary lifting to jump over complete “blocks” that fit entirely within the interval.

• When at cur, its block is \([cur,\mathrm{nge}[cur)-1]\)
• The condition for this block to fit entirely within \(R\) is \(\mathrm{nge}[cur] \le R+1\)

So with limit = R+1, iterate from the largest \(k\) downward: if up[k][cur] <= limit, then: - res += sw[k][cur] - cur = up[k][cur]

For the remaining cur, the block may be cut short, so we add: - The number of mountains with height \(H[cur]\) in \([cur,R]\) using binary search, and we’re done.

Complexity

• Time complexity:
  
  • Building \(\mathrm{nge}\): \(O(N)\)
    
  • Computing \(w[i]\) (binary search for each \(i\)): \(O(N\log N)\)
    
  • Building the binary lifting table: \(O(N\log N)\)
    
  • Each query: \(O(\log N)\)
    Overall: \(O\big((N+Q)\log N\big)\)
• Space complexity: \(O(N\log N)\) (binary lifting table)

Implementation Notes

• The “not visible” condition uses strictly taller (\(>\)), so mountains of the same height do not block each other and both are visible. Therefore, \(\mathrm{nge}\) is defined as “next strictly greater,” and we pop elements with <=.

• The condition for “the block fits entirely” in a query is nge[cur] <= R+1 (equivalently nge[cur]-1 <= R).

• Since we hold \(N\log N\) arrays in Python, we use array('I') to reduce memory usage.

• For faster input, we use a hand-written parser reading from sys.stdin.buffer.read().

  Source Code

import sys
from bisect import bisect_right
from array import array

data = sys.stdin.buffer.read()
m = len(data)
p = 0

def ni():
    global p
    while p < m and data[p] <= 32:
        p += 1
    x = 0
    while p < m and data[p] > 32:
        x = x * 10 + (data[p] - 48)
        p += 1
    return x

N = ni()
Q = ni()

H = [0] * (N + 2)
pos = {}
rank = [0] * (N + 2)

for i in range(1, N + 1):
    h = ni()
    H[i] = h
    lst = pos.get(h)
    if lst is None:
        pos[h] = [i]
        rank[i] = 0
    else:
        rank[i] = len(lst)
        lst.append(i)

# Next strictly greater element to the right
nge = [0] * (N + 2)
stack = []
for i in range(N, 0, -1):
    hi = H[i]
    while stack and H[stack[-1]] <= hi:
        stack.pop()
    nge[i] = stack[-1] if stack else N + 1
    stack.append(i)
nge[N + 1] = N + 1

# Weight: number of indices t in [i, nge[i)-1] with H[t] == H[i]
w = [0] * (N + 2)
br = bisect_right
for i in range(1, N + 1):
    end = nge[i] - 1
    lst = pos[H[i]]
    w[i] = br(lst, end) - rank[i]
w[N + 1] = 0

LOG = (N + 2).bit_length()
up = [array('I', [0]) * (N + 2) for _ in range(LOG)]
sw = [array('I', [0]) * (N + 2) for _ in range(LOG)]

up0 = up[0]
sw0 = sw[0]
for i in range(1, N + 2):
    up0[i] = nge[i]
    sw0[i] = w[i]

for k in range(1, LOG):
    up_prev = up[k - 1]
    sw_prev = sw[k - 1]
    up_k = up[k]
    sw_k = sw[k]
    for i in range(1, N + 2):
        mid = up_prev[i]
        up_k[i] = up_prev[mid]
        sw_k[i] = sw_prev[i] + sw_prev[mid]

ks = list(range(LOG - 1, -1, -1))
out = []
for _ in range(Q):
    L = ni()
    R = ni()
    limit = R + 1

    cur = L
    res = 0
    for k in ks:
        nxt = up[k][cur]
        if nxt <= limit:
            res += sw[k][cur]
            cur = nxt

    if cur <= R:
        h = H[cur]
        res += br(pos[h], R) - rank[cur]

    out.append(str(res))

sys.stdout.write("\n".join(out))

---

This editorial was generated by gpt-5.2-high.