Overview

This problem requires calculating the visibility score for each building and efficiently answering multiple queries about how many buildings have a score greater than or equal to a given threshold.

Analysis

The visibility score of each building \(i\) is determined by the positions of the nearest taller buildings to its left and right (\(L_i\) and \(R_i\)). Naively searching left and right linearly for each building takes \(O(N^2)\) time, which is too slow since \(N\) can be up to \(2 \times 10^5\).

This problem requires efficiently finding the “next taller building” to the left and right for each building. This can be computed in \(O(N)\) time using a classic technique with a stack (Monotonic Stack). For query processing, by counting the frequency of each score and precomputing a cumulative sum (suffix sum), each query can be answered in \(O(1)\).

Algorithm

1. Finding the next taller building to the left and right:

   • Scan from left to right, using a monotonically decreasing stack to find \(L_i\), the next taller building to the left of each building \(i\)
   • Scan from right to left, similarly finding \(R_i\), the next taller building to the right

2. Score calculation:

   • For each building \(i\), calculate the score based on whether \(L_i\) and \(R_i\) exist:
     • Both exist: \(score = R_i - L_i - 1\)
     • Only left does not exist: \(score = R_i - 1\)
     • Only right does not exist: \(score = N - L_i\)
     • Neither exists: \(score = N\)

3. Frequency count and cumulative sum:

   • Count the frequency of each score value
   • Precompute the suffix sum (\(suffix\_sum[x]\) = number of buildings with a score of \(x\) or more)

4. Query processing:

   • For each query \(X_k\), output the precomputed \(suffix\_sum[X_k]\)

Complexity

• Time complexity: \(O(N + Q)\)
  • Left and right stack processing: \(O(N)\)
  • Score calculation: \(O(N)\)
  • Frequency count and cumulative sum: \(O(N)\)
  • Query processing: \(O(Q)\)
• Space complexity: \(O(N)\)
  • Arrays \(left\), \(right\), \(scores\), \(freq\), \(suffix\_sum\), etc., are all \(O(N)\)

Implementation Notes

• In the stack processing, since no two buildings have equal heights, we can use “less than or equal to” instead of “strictly less than” for comparisons

• Using 1-indexed arrays makes it easier to match the problem’s description

• Representing non-existence with 0 allows unified handling of conditional branches

• When computing the suffix sum, implement it so that \(suffix\_sum[x] = freq[x] + freq[x+1] + ... + freq[N]\)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); Q = int(next(it))
    H = [0] * (N+1)
    for i in range(1, N+1):
        H[i] = int(next(it))
    queries = [int(next(it)) for _ in range(Q)]
    
    left = [0] * (N+2)
    right = [0] * (N+2)
    stack = []
    for i in range(1, N+1):
        while stack and H[stack[-1]] <= H[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        else:
            left[i] = 0
        stack.append(i)
    
    stack = []
    for i in range(N, 0, -1):
        while stack and H[stack[-1]] <= H[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        else:
            right[i] = 0
        stack.append(i)
    
    scores = [0] * (N+1)
    for i in range(1, N+1):
        l = left[i]
        r = right[i]
        if l == 0 and r == 0:
            score = N
        elif l == 0:
            score = r - 1
        elif r == 0:
            score = N - l
        else:
            score = r - l - 1
        scores[i] = score
    
    freq = [0] * (N+2)
    for i in range(1, N+1):
        if scores[i] <= N:
            freq[scores[i]] += 1
    
    suffix_sum = [0] * (N+2)
    suffix_sum[N] = freq[N]
    for x in range(N-1, 0, -1):
        suffix_sum[x] = suffix_sum[x+1] + freq[x]
    
    res = []
    for x in queries:
        res.append(str(suffix_sum[x]))
    
    print("\n".join(res))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.