概要

各ビルの見晴らしスコアを計算し、与えられた閾値以上のスコアを持つビルの数を複数のクエリに対して効率的に答える問題です。

考察

各ビル \(i\) の見晴らしスコアは、左右それぞれの方向で最も近い自分より高いビル（\(L_i\) と \(R_i\)）の位置によって決まります。素朴に各ビルに対して左右を線形探索すると \(O(N^2)\) 時間かかり、\(N\) が最大 \(2 \times 10^5\) なので間に合いません。

この問題は、各ビルに対して左右の「次に高いビル」を効率的に求める必要があります。これはスタックを用いた典型的な手法（Monotonic Stack）で \(O(N)\) 時間で計算できます。また、クエリ処理にはスコアの頻度を数え、累積和（接尾辞和）を事前計算することで、各クエリに \(O(1)\) で答えられます。

アルゴリズム

1. 左右の次に高いビルの特定:

   • 左から右へスキャンし、単調減少スタックを用いて各ビル \(i\) に対する左側の次に高いビル \(L_i\) を求めます
   • 右から左へスキャンし、同様に右側の次に高いビル \(R_i\) を求めます

2. スコア計算:

   • 各ビル \(i\) について、\(L_i\) と \(R_i\) の存在状況に応じてスコアを計算します:
     • 両方存在: \(score = R_i - L_i - 1\)
     • 左のみ存在しない: \(score = R_i - 1\)
     • 右のみ存在しない: \(score = N - L_i\)
     • 両方存在しない: \(score = N\)

3. 頻度カウントと累積和:

   • 各スコア値の出現頻度を数えます
   • 接尾辞和（\(suffix\_sum[x] = x\) 以上のスコアを持つビルの数）を事前計算します

4. クエリ処理:

   • 各クエリ \(X_k\) に対して、事前計算した \(suffix\_sum[X_k]\) を出力します

計算量

• 時間計算量: \(O(N + Q)\)
  • 左右のスタック処理: \(O(N)\)
  • スコア計算: \(O(N)\)
  • 頻度カウントと累積和: \(O(N)\)
  • クエリ処理: \(O(Q)\)
• 空間計算量: \(O(N)\)
  • 配列 \(left\), \(right\), \(scores\), \(freq\), \(suffix\_sum\) などすべて \(O(N)\)

実装のポイント

• スタック処理では、等しい高さのビルがないため「小なり」ではなく「小なりイコール」で比較できます

• 配列のインデックスは1-indexedで扱うと問題の記述と一致して扱いやすい

• 存在しない場合の処理を0で表現することで、条件分岐を統一して扱えます

• 接尾辞和を計算する際、\(suffix\_sum[x] = freq[x] + freq[x+1] + ... + freq[N]\) となるように実装します

  ソースコード

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

この解説は deepseekv3 によって生成されました。