概要

\(N\) 棟のビルが並んでおり、各ビルについて「自分より高いビルに挟まれた範囲（または端まで）」の棟数を「見晴らしスコア」と定義します。与えられた \(Q\) 個のクエリに対し、スコアが \(X_k\) 以上であるビルの数を素早く求める問題です。

考察

各ビル \(i\) について、以下の 2 つの情報を知る必要があります。 - \(L_i\): ビル \(i\) より左側にあり、ビル \(i\) より高いビルのうち最も近いものの番号 - \(R_i\): ビル \(i\) より右側にあり、ビル \(i\) より高いビルのうち最も近いものの番号

1. 素朴なアプローチ

各ビル \(i\) に対して左右を順番に走査して \(L_i, R_i\) を探すと、1 つのビルにつき最悪 \(O(N)\) かかります。全体で \(O(N^2)\) となり、 \(N=2 \times 10^5\) の制約下では実行時間制限に間に合いません。

2. 効率的な探索（モノトニックスタック）

「自分より大きい（または小さい）要素が次に現れる位置」を求める問題は、スタックを用いることで各要素を 1 回ずつ出し入れするだけの \(O(N)\) で解くことができます。これをモノトニックスタックと呼びます。

例えば \(R_i\) を求める場合、左から順にビルを見ていき、スタックには「まだ自分より高いビルが見つかっていないビルの番号」を保持します。現在のビルがスタックの先頭にあるビルより高い場合、その現在のビルがスタックの先頭にとっての「最も近い右側の高いビル」になります。

3. スコアの計算とクエリ処理

問題文にある 4 つの条件は、仮想的なビルとして「ビル \(0\) のさらに左（位置 \(-1\)）」と「ビル \(N\) のさらに右（位置 \(N\)）」に、どのビルよりも高い壁があると考えることで、すべて \(R_i - L_i - 1\) という一つの式に統合できます。

全ビルのスコアを計算した後は、各スコアの出現回数をカウントし、累積和（後ろからの累積和）をとることで、「スコア \(X\) 以上のビルの数」を \(O(1)\) で答えられるようになります。

アルゴリズム

1. \(R_i\) の算出: 左から右へ走査し、スタックを用いて各ビル \(i\) の右側にある直近の高いビルのインデックス \(R_i\) を求める。存在しない場合は \(N\) とする。
2. \(L_i\) の算出: 右から左へ走査し、同様に左側にある直近の高いビルのインデックス \(L_i\) を求める。存在しない場合は \(-1\) とする。
3. スコアの集計: 各 \(i\) について \(S_i = R_i - L_i - 1\) を計算し、スコアごとの出現頻度を配列 count に記録する。
4. 累積和の計算: count 配列を後ろから累積和し、count[x] が「スコア \(x\) 以上のビルの総数」を表すようにする。
5. クエリ応答: 各 \(X_k\) に対して count[X_k] を出力する。

計算量

• 時間計算量: \(O(N + Q)\)
  • \(L_i, R_i\) の算出に \(O(N)\)、スコアの集計と累積和に \(O(N)\)、クエリ応答に \(O(Q)\) かかります。
• 空間計算量: \(O(N)\)
  • 高さ、左右のインデックス、スコアの集計配列などを保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 境界値の扱い: \(L_i\) が存在しない場合は \(-1\)、\(R_i\) が存在しない場合は \(N\) と置くことで、問題文の複雑な条件分岐を \(R_i - L_i - 1\) という簡潔な計算式にまとめることができます。

• 高速な入出力: \(N, Q\) が大きいため、Python の場合は sys.stdin.read().split() や sys.stdout.write を使用して入出力を高速化するのが定石です。

  ソースコード

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

---

この解説は gemini-3-flash-thinking によって生成されました。