Overview

This is a problem where we calculate the “view score” for each building and process queries to answer how many buildings have a score greater than or equal to a specified value.

Analysis

In this problem, for each building \(i\), we need to find “where the first taller building is to the left and right,” and determine the score based on that. The score is defined as the length of the interval up to the “first taller building” on each side.

Why a naive approach is too slow

If we naively perform a linear search to the left and right for each building to find the nearest taller building, the time complexity becomes \(O(N^2)\), which will result in TLE given the constraint \(N \leq 2 \times 10^5\).

Key to optimization

The problem of finding “where the first value greater than a given element is to the right (or left)” can be efficiently solved using a stack. This is the classic “Next Greater Element” problem.

• Right direction: By processing from the end using a stack, we can find the first greater element to the right of each element in \(O(N)\).
• Left direction: Process similarly from the beginning.

This allows us to compute the view score for all buildings in \(O(N)\).

After that, by sorting the list of scores, we can efficiently determine “the number of buildings with a score of at least \(X_k\)” for each query using binary search.

Algorithm

1. For each building \(i\):
   • Find the position \(R_i\) of the first taller building to the right using a stack.
   • Find the position \(L_i\) of the first taller building to the left using a stack.
2. Calculate the view score for each building as follows:
   • If both \(L_i\) and \(R_i\) exist: \(R_i - L_i - 1\)
   • If only one exists: \(R_i - 1\) or \(N - L_i\)
   • If neither exists: \(N\)
3. Sort the list of scores.
4. For each query \(X_k\), use binary search to find “the number of buildings with a score of at least \(X_k\).”

Complexity

• Time complexity: \(O(N + Q \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• When using a stack to find the first taller building on each side, store indices in the stack to carry position information.

• Be careful with the conditional branching for view score calculation (especially boundary cases and handling of None values).

• Use bisect_left for binary search to efficiently retrieve the count of qualifying elements from the sorted list.

  Source Code

import sys
from bisect import bisect_left, bisect_right
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    Q = int(data[1])
    H = list(map(int, data[2:2+N]))
    X = list(map(int, data[2+N:2+N+Q]))
    
    # 左右の最近傍の高さが高いビルを求める
    # 右方向
    R = [None] * N
    stack = []
    for i in range(N-1, -1, -1):
        h = H[i]
        while stack and H[stack[-1]] <= h:
            stack.pop()
        if stack:
            R[i] = stack[-1]
        else:
            R[i] = None
        stack.append(i)
        
    # 左方向
    L = [None] * N
    stack = []
    for i in range(N):
        h = H[i]
        while stack and H[stack[-1]] <= h:
            stack.pop()
        if stack:
            L[i] = stack[-1]
        else:
            L[i] = None
        stack.append(i)
    
    # 各ビルの見晴らしスコアを計算
    scores = []
    for i in range(N):
        l = L[i]
        r = R[i]
        if l is not None and r is not None:
            score = r - l - 1
        elif l is None and r is not None:
            score = r
        elif l is not None and r is None:
            score = N - l - 1
        else:
            score = N
        scores.append(score)
    
    # スコアのリストをソートして、クエリに対して二分探索
    scores.sort()
    
    results = []
    for x in X:
        # scoresの中で x 以上の要素の個数
        idx = bisect_left(scores, x)
        count = N - idx
        results.append(count)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.