Overview

For each building, find the “first taller building appearing on each side (left and right),” compute the length of the interval sandwiched between them (the view score), and for each query \(X\), quickly answer “how many buildings have a score of at least \(X\).”

Analysis

The view score is determined immediately once we know \(L_i\) and \(R_i\) — the nearest buildings taller than building \(i\) on its left and right, respectively.

• If both exist, the score is \(R_i - L_i - 1\)
• If only one exists, it’s the length of the interval extending to the corresponding end
• If neither exists, the score is \(N\) (the entire street)

Why the naive approach fails

For each building \(i\), scanning left and right to find the “first taller building” takes \(O(N)\) in the worst case. Doing this for all buildings results in \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).

Solution

“The nearest larger element on each side for every element” can be found in overall \(O(N)\) using a Monotonic Stack.
After computing all scores, we count the number of buildings for each score value, then take a suffix sum (cumulative sum from the back) so that “count of scores \(\ge X\)” can be answered in \(O(1)\) per query.

Algorithm

1. Find the nearest taller building to the left \(L_i\) (monotone decreasing stack)

Process buildings from left to right, maintaining a stack of indices in decreasing order of height (the top of the stack has the smallest height).

• When processing building \(i\), if the top of the stack is shorter than \(i\) (\(H[\text{top}] < H[i]\)), then it cannot be “a taller building to the left of \(i\),” so pop it
• After popping, the new top of the stack (if it exists) is the “nearest taller building to the left” = \(L_i\)
• Finally, push \(i\) onto the stack

This computes each \(L_i\) in \(O(1)\) amortized, giving \(O(N)\) overall.

2. Find the nearest taller building to the right \(R_i\)

Process from right to left using the same logic to obtain \(R_i\).

3. Compute scores and count them in a frequency array freq

In the code, \(L[i]\) and \(R[i]\) are stored using 0-indexing, but to simplify score calculation, we align the “boundaries” in the following 1-index style:

• Left boundary lb:
  • If \(L_i\) exists: lb = L[i] + 1 (= the 1-indexed position of the taller building on the left)
  • If it doesn’t exist: lb = 0 (outside the left end of the street)
• Right boundary rb:
  • If \(R_i\) exists: rb = R[i] + 1 (= the 1-indexed position of the taller building on the right)
  • If it doesn’t exist: rb = N + 1 (outside the right end of the street)

Then the score is always uniformly computed as [ \text{score} = rb - lb - 1 ] (this naturally handles the cases where one or both boundaries don’t exist).

For each building, compute the score and do freq[score] += 1.

Concrete example

With \(N=5\), if no taller building is found on either side of a certain building, then lb=0, rb=6, so [ \text{score} = 6 - 0 - 1 = 5 ] which gives “the entire \(N\).”

4. Convert to “number of buildings with score \(\ge X\)” (suffix cumulative sum)

Since freq[s] is “the number of buildings with score exactly \(s\),” what we want is [ #{ i \mid \text{score}_i \ge X } ] So we update from the back: [ freq[x] \leftarrow freq[x] + freq[x+1] ] After this, freq[x] represents the count of buildings with score \(\ge x\).

5. Answer each query by outputting freq[X_k]

Each query is answered in \(O(1)\).

Complexity

• Time complexity: \(O(N + Q)\)
  (Two monotonic stack passes in \(O(N)\), frequency counting and suffix sum in \(O(N)\), query answering in \(O(Q)\))
• Space complexity: \(O(N)\)
  (\(L, R, freq, stack\), etc.)

Implementation Notes

• “Taller” means strictly \(>\): Since all heights are distinct, the stack pop condition H[top] < H[i] (not <=) is correct.

• Unifying boundary handling makes things easier: By treating the left end as 0 and the right end as N+1, the score can always be computed as rb - lb - 1.

• freq has size N+2: Since we reference freq[x+1], we allocate extra space as a sentinel.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    H = [next(it) for _ in range(N)]

    L = [-1] * N
    st = []
    for i in range(N):
        hi = H[i]
        while st and H[st[-1]] < hi:
            st.pop()
        L[i] = st[-1] if st else -1
        st.append(i)

    R = [-1] * N
    st = []
    for i in range(N - 1, -1, -1):
        hi = H[i]
        while st and H[st[-1]] < hi:
            st.pop()
        R[i] = st[-1] if st else -1
        st.append(i)

    freq = [0] * (N + 2)  # 1..N
    for i in range(N):
        lb = L[i] + 1 if L[i] != -1 else 0          # boundary index (0-based), or -1 -> use 0 in formula below
        rb = R[i] + 1 if R[i] != -1 else N + 1      # boundary index (1..N), or none -> N+1
        # Convert to 1-based boundary indices: left boundary = L[i]+1 (or 0), right boundary = R[i]+1 (or N+1)
        score = rb - lb - 1
        freq[score] += 1

    for x in range(N - 1, 0, -1):
        freq[x] += freq[x + 1]

    out = []
    for _ in range(Q):
        x = next(it)
        out.append(str(freq[x]))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.