Overview

\(N\) buildings are lined up, and for each building, the “view score” is defined as the number of buildings in the range bounded by taller buildings on each side (or extending to the edge). For each of the given \(Q\) queries, the task is to quickly determine the number of buildings whose score is at least \(X_k\).

Analysis

For each building \(i\), we need to know the following two pieces of information: - \(L_i\): The index of the nearest building to the left of building \(i\) that is taller than building \(i\) - \(R_i\): The index of the nearest building to the right of building \(i\) that is taller than building \(i\)

1. Naive Approach

If we scan left and right for each building \(i\) to find \(L_i\) and \(R_i\), it takes \(O(N)\) in the worst case per building. This results in \(O(N^2)\) overall, which is too slow under the constraint \(N = 2 \times 10^5\).

2. Efficient Search (Monotonic Stack)

The problem of finding “the next position where a larger (or smaller) element appears” can be solved in \(O(N)\) using a stack, where each element is pushed and popped at most once. This technique is called a monotonic stack.

For example, to compute \(R_i\), we scan buildings from left to right, maintaining a stack of “building indices that have not yet found a taller building to their right.” If the current building is taller than the building at the top of the stack, then the current building becomes the “nearest taller building to the right” for the building at the top of the stack.

3. Score Calculation and Query Processing

The four conditions described in the problem statement can all be unified into a single formula \(R_i - L_i - 1\) by imagining virtual buildings: a wall taller than any building at position \(-1\) (to the left of building \(0\)) and at position \(N\) (to the right of building \(N-1\)).

After computing the scores for all buildings, we count the frequency of each score and take a suffix cumulative sum so that we can answer “the number of buildings with score at least \(X\)” in \(O(1)\).

Algorithm

1. Computing \(R_i\): Scan from left to right, using a stack to find the index \(R_i\) of the nearest taller building to the right of each building \(i\). If none exists, set \(R_i = N\).
2. Computing \(L_i\): Scan from right to left, similarly finding the index \(L_i\) of the nearest taller building to the left of each building \(i\). If none exists, set \(L_i = -1\).
3. Score Aggregation: For each \(i\), compute \(S_i = R_i - L_i - 1\) and record the frequency of each score in an array count.
4. Cumulative Sum Calculation: Compute the suffix cumulative sum of the count array so that count[x] represents “the total number of buildings with score at least \(x\).”
5. Query Response: For each \(X_k\), output count[X_k].

Complexity

• Time Complexity: \(O(N + Q)\)
  • Computing \(L_i\) and \(R_i\) takes \(O(N)\), score aggregation and cumulative sum take \(O(N)\), and answering queries takes \(O(Q)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the heights, left/right indices, and the score frequency array.

Implementation Notes

• Handling Boundary Values: By setting \(L_i = -1\) when no taller building exists to the left and \(R_i = N\) when none exists to the right, we can consolidate the complex conditional branching in the problem statement into the concise formula \(R_i - L_i - 1\).

• Fast I/O: Since \(N\) and \(Q\) can be large, in Python it is standard practice to use sys.stdin.read().split() and sys.stdout.write to speed up input and output.

  Source Code

import sys

def solve():
    # Read all input from standard input and split into words for fast processing
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not input_data:
        return
    
    # N is the number of buildings, Q is the number of queries
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # H stores the heights of the buildings from 1 to N.
    # We use 0-based indexing for calculations.
    H = [0] * N
    for i in range(N):
        H[i] = int(input_data[2 + i])
        
    # R[i] will store the 0-based index of the nearest taller building to the right of building i.
    # If no such building exists, we use N as a boundary index.
    R = [N] * N
    stack = []
    for i in range(N):
        h_i = H[i]
        # While the current building is taller than the building at the top of the stack,
        # it is the nearest taller building to the right for those buildings.
        while stack and H[stack[-1]] < h_i:
            R[stack.pop()] = i
        stack.append(i)
        
    # L[i] will store the 0-based index of the nearest taller building to the left of building i.
    # If no such building exists, we use -1 as a boundary index.
    L = [-1] * N
    stack = []
    for i in range(N - 1, -1, -1):
        h_i = H[i]
        # While the current building is taller than the building at the top of the stack,
        # it is the nearest taller building to the left for those buildings.
        while stack and H[stack[-1]] < h_i:
            L[stack.pop()] = i
        stack.append(i)
        
    # The "viewing score" for building i is defined as the number of buildings
    # in the continuous interval containing building i until we hit a taller building
    # or the end of the street. In our 0-indexed system with boundaries, 
    # this is exactly R[i] - L[i] - 1.
    # We count the frequency of each possible score (from 1 to N).
    count = [0] * (N + 2)
    for i in range(N):
        score = R[i] - L[i] - 1
        # score is guaranteed to be between 1 and N given the problem constraints
        if score > N:
            score = N
        count[score] += 1
        
    # Suffix sums: count[x] will store the number of buildings with score >= x.
    # We compute this in O(N) by iterating backwards from N to 1.
    for i in range(N, 0, -1):
        count[i] += count[i+1]
        
    # Answer each query using the precomputed suffix sums.
    results = []
    # Queries are provided starting from input_data[2 + N]
    for i in range(Q):
        X = int(input_data[2 + N + i])
        if X > N:
            # No building can have a score greater than N
            results.append("0")
        else:
            # The count of buildings with score >= X is retrieved in O(1)
            results.append(str(count[X]))
            
    # Output all results separated by newlines for efficiency
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

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