概要

各ビルの「見晴らしスコア」を計算し、指定された値以上のスコアを持つビルの数を答えるクエリ処理を行う問題です。

考察

この問題では、各ビル \(i\) について「自分より高いビルが左右どこにあるか」を求め、それによってスコアを決定します。このスコアの定義は、左右の「最初に自分より高いビル」までの区間の長さとなっています。

素朴な方法では間に合わない理由

ナイーブに各ビルについて右と左を線形探索して最近傍の高いビルを見つけると、計算量が \(O(N^2)\) になってしまい、制約 \(N \leq 2 \times 10^5\) ではTLEしてしまいます。

高速化のポイント

「ある要素より右（または左）で初めて大きい値がどこにあるか」という問題は、スタックを使うことで効率的に求めることができます。これは典型的な「Next Greater Element」の問題です。

• 右方向：後ろからスタックを使って処理することで、各要素より右の最初の大きな要素を \(O(N)\) で求められます。
• 左方向：前から同様に処理します。

これにより、全ビルの見晴らしスコアが \(O(N)\) で求められます。

その後、スコアのリストをソートしておけば、各クエリに対して二分探索で「スコアが \(X_k\) 以上であるビルの数」を高速に求めることができます。

アルゴリズム

1. 各ビル \(i\) に対して：
   • 右方向で最初に自分より高いビルの位置 \(R_i\) をスタックを使って求める。
   • 左方向で最初に自分より高いビルの位置 \(L_i\) をスタックを使って求める。
2. 各ビルの見晴らしスコアを以下のように計算：
   • \(L_i\) と \(R_i\) がある場合：\(R_i - L_i - 1\)
   • 片方だけある場合：\(R_i - 1\) または \(N - L_i\)
   • どちらもない場合：\(N\)
3. スコアのリストをソートする。
4. 各クエリ \(X_k\) に対して、二分探索で「スコアが \(X_k\) 以上であるビルの数」を求める。

計算量

• 時間計算量: \(O(N + Q \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• スタックを使って左右の最初の高いビルを見つける際、インデックスをスタックに入れることで位置情報を持ち回せる。

• 見晴らしスコアの条件分岐は慎重に行うこと（特に境界や None の扱い）。

• 二分探索には bisect_left を使い、ソート済みリストから該当する要素数を高速に取得する。

  ソースコード

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()

この解説は qwen3-coder-480b によって生成されました。