Overview

For each building, find the nearest “taller building” on both the left and right sides, compute the length of the interval between them as the “view score,” and for each query, answer the number of buildings whose score is at least \(X_k\).

Analysis

Key Insight: Next Greater Element

For each building \(i\), the desired \(R_i\) (the nearest taller building to the right) and \(L_i\) (the nearest taller building to the left) are exactly the well-known Next Greater Element (NGE) problem in competitive programming.

Problem with the Naive Approach

If we naively scan left and right for each building, it takes \(O(N)\) per building in the worst case, resulting in \(O(N^2)\) overall. This will TLE for \(N \leq 2 \times 10^5\).

Solution: Monotonic Stack

Using a Monotonic Stack, we can compute \(R_i\) and \(L_i\) for all buildings in \(O(N)\) each.

Handling Queries

Scanning all scores for each of the \(Q\) queries would be \(O(NQ)\), which risks TLE. By precomputing a suffix sum of the scores, we can answer each query in \(O(1)\).

Algorithm

Step 1: Computing \(R_i\) (Next Greater Element to the Right)

Scan the array from left to right while maintaining a monotonic stack (where the heights of elements in the stack are in monotonically decreasing order).

• When processing building \(i\), if the building \(j\) at the top of the stack has height \(H[j]\) less than \(H[i]\), then building \(i\) is the “nearest taller building to the right” for building \(j\). Pop \(j\) from the stack and set \(R_j = i\).
• Repeat this as long as the condition holds, then push \(i\) onto the stack.

Concrete example (\(H = [3, 1, 4, 1, 5]\)): - Building 0 (height 3): Stack empty → push. Stack=[0] - Building 1 (height 1): \(H[0]=3 > 1\) so no pop → push. Stack=[0,1] - Building 2 (height 4): \(H[1]=1 < 4\) → \(R_1 = 2\). \(H[0]=3 < 4\) → \(R_0 = 2\). Push. Stack=[2] - Building 3 (height 1): No pop → push. Stack=[2,3] - Building 4 (height 5): \(H[3]=1 < 5\) → \(R_3 = 4\). \(H[2]=4 < 5\) → \(R_2 = 4\). Push. Stack=[4] - Building 4 remaining in the stack has no \(R_4\).

Step 2: Computing \(L_i\) (Next Greater Element to the Left)

Scan the array from right to left and use a similar monotonic stack. When processing building \(i\), if the building \(j\) at the top of the stack (\(j > i\)) has height less than \(H[i]\), set \(L_j = i\).

Step 3: Computing the View Score

When using 0-indexed management, convert the 1-indexed formulas from the problem statement.

Condition	1-indexed formula	0-indexed formula
Both \(L_i\) and \(R_i\) exist	\(R_i - L_i - 1\)	\(ri - li - 1\)
Only \(R_i\) exists	\(R_i - 1\)	\(ri\)
Only \(L_i\) exists	\(N - L_i\)	\(N - li - 1\)
Neither exists	\(N\)	\(N\)

Step 4: Answering Queries

1. Create an array \(\text{count}[s]\) (the number of buildings with score \(s\)).
2. Compute the suffix sum from the back: \(\text{suffix\_count}[x] = \sum_{s=x}^{N} \text{count}[s]\) (the number of buildings with score at least \(x\)).
3. For each query \(X_k\), output \(\text{suffix\_count}[X_k]\).

Complexity

• Time complexity: \(O(N + Q)\)
  • Computing \(R_i\) and \(L_i\) with the monotonic stack is \(O(N)\) each
  • Score computation is \(O(N)\)
  • Building the suffix sum is \(O(N)\)
  • Answering each query is \(O(1) \times Q\)
• Space complexity: \(O(N + Q)\)

Implementation Notes

• Be careful with 0-indexed and 1-indexed conversion: The problem statement uses 1-indexed definitions, but if processing in 0-indexed within the code, the score computation formulas must be converted accurately.

• Direction of the monotonic stack: \(R_i\) is computed by scanning left→right, and \(L_i\) by scanning right→left. Both follow the same principle of “pop and record when a value larger than the stack’s top element arrives.”

• Preprocess with suffix sum: To avoid linear scanning per query, aggregate the score distribution first and build a suffix sum, speeding up each query to \(O(1)\).

  Source Code

import sys
from collections import defaultdict

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 = [int(input_data[idx + i]) for i in range(Q)]
    idx += Q
    
    # Find R_i (next greater element to the right) using monotonic stack
    R = [0] * N  # 0-indexed, store 1-indexed or use sentinel
    # We'll use 1-indexed positions internally
    # R[i] = index (1-indexed) of next greater to the right, or -1 if none
    stack = []
    R_val = [-1] * N
    for i in range(N):
        while stack and H[stack[-1]] < H[i]:
            R_val[stack.pop()] = i  # 0-indexed
        stack.append(i)
    
    # Find L_i (next greater element to the left) using monotonic stack
    L_val = [-1] * N
    stack = []
    for i in range(N - 1, -1, -1):
        while stack and H[stack[-1]] < H[i]:
            L_val[stack.pop()] = i  # 0-indexed
        stack.append(i)
    
    # Compute scores
    # Convert to 1-indexed for the formula
    scores = [0] * N
    for i in range(N):
        li = L_val[i]  # 0-indexed or -1
        ri = R_val[i]  # 0-indexed or -1
        
        has_L = (li != -1)
        has_R = (ri != -1)
        
        if has_L and has_R:
            # 1-indexed: R_i - L_i - 1
            # In 0-indexed: (ri+1) - (li+1) - 1 = ri - li - 1
            scores[i] = ri - li - 1
        elif has_R and not has_L:
            # 1-indexed: R_i - 1
            # In 0-indexed: (ri+1) - 1 = ri
            scores[i] = ri
        elif has_L and not has_R:
            # 1-indexed: N - L_i
            # In 0-indexed: N - (li+1) = N - li - 1
            scores[i] = N - li - 1
        else:
            scores[i] = N
    
    # Build suffix count: for each score value, count how many buildings have score >= X
    # Create count array
    count = [0] * (N + 2)
    for s in scores:
        if 1 <= s <= N:
            count[s] += 1
    
    # suffix_count[x] = number of buildings with score >= x
    suffix_count = [0] * (N + 2)
    for x in range(N, 0, -1):
        suffix_count[x] = suffix_count[x + 1] + count[x]
    
    out = []
    for k in range(Q):
        x = queries[k]
        out.append(str(suffix_count[x]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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