概要

各ビルについて「左右で最初に現れる自分より高いビル」を求め、その間に挟まれた区間の長さ（見晴らしスコア）を計算し、質問 \(X\) ごとに「スコアが \(X\) 以上の個数」を高速に答えます。

考察

見晴らしスコアは、ビル \(i\) の左右にある「自分より高いビルのうち最も近いもの」\(L_i, R_i\) が分かれば一発で決まります。

• 両方あるなら、スコアは \(R_i - L_i - 1\)
• 片方しかないなら、端まで伸びた区間の長さ
• 両方ないなら、全体で \(N\)

素朴解がダメな理由

各ビル \(i\) について左へ・右へ走査して「最初に高いビル」を探すと、最悪で \(O(N)\) かかります。これを全ビルに対して行うと \(O(N^2)\) となり、\(N \le 2\times 10^5\) では間に合いません。

解決策

「各要素の左右で最も近い“より大きい要素”」は 単調スタック（Monotonic Stack）で全体 \(O(N)\) で求められます。
スコアが全部求まった後は、スコア値ごとの個数を数え上げ、累積（後ろからの和）を取れば「\(X\) 以上」を各クエリ \(O(1)\) で答えられます。

アルゴリズム

1. 左側の最近の高いビル \(L_i\) を求める（単調減少スタック）

左から順に見ていき、スタックには「高さが高い順（上ほど低い）」になるように index を保持します。

• ビル \(i\) を見るとき、スタック上端が自分より低い（\(H[\text{top}] < H[i]\)）なら、それは「\(i\) の左側で \(i\) より高いビル」にはなれないので pop
• pop 後のスタック上端が（存在すれば）「左で最も近い自分より高いビル」＝\(L_i\)
• 最後に \(i\) を push

これで各 \(L_i\) が \(O(1)\) 償却で求まり、全体 \(O(N)\) です。

2. 右側の最近の高いビル \(R_i\) を求める

右から左へ同様に処理すれば \(R_i\) も求まります（ロジックは同じ）。

3. スコアを計算して度数分布 freq に数える

コードでは 0-index で \(L[i], R[i]\) を持ちますが、スコア計算を簡単にするため「境界」を次の 1-index 風に揃えています。

• 左境界 lb：
  • \(L_i\) が存在するなら lb = L[i] + 1（= 左の高いビルの番号）
  • 存在しないなら lb = 0（通りの左端の外側）
• 右境界 rb：
  • \(R_i\) が存在するなら rb = R[i] + 1（= 右の高いビルの番号）
  • 存在しないなら rb = N + 1（通りの右端の外側）

するとスコアは常に [ \text{score} = rb - lb - 1 ] で統一できます（両端がないケースも自然に含まれます）。

各ビルの score を求めて freq[score] += 1 とします。

具体例

\(N=5\) で、あるビルの左右に高いビルが見つからない場合は lb=0, rb=6 なので
[ \text{score} = 6 - 0 - 1 = 5 ] となり「全体 \(N\)」が得られます。

4. 「スコアが \(X\) 以上」の個数に変換（後ろから累積和）

freq[s] が「スコアがちょうど \(s\) のビル数」なので、求めたいのは [ #{ i \mid \text{score}_i \ge X } ] です。そこで後ろから [ freq[x] \leftarrow freq[x] + freq[x+1] ] と更新すると、freq[x] が「\(x\) 以上」の個数になります。

5. 各クエリは freq[X_k] を出力

クエリごとに \(O(1)\) で答えられます。

計算量

• 時間計算量: \(O(N + Q)\)
  （単調スタック 2 回が \(O(N)\)、度数集計と累積が \(O(N)\)、クエリ回答が \(O(Q)\)）
• 空間計算量: \(O(N)\)
  （\(L, R, freq, stack\) など）

実装のポイント

• 「より高い」は厳密に \(>\)：高さはすべて異なるので、スタックの pop 条件は H[top] < H[i]（<= ではない）でOKです。

• 境界の扱いを統一すると楽：左端を 0、右端を N+1 とみなすことで、スコアを常に rb - lb - 1 で計算できます。

• freq は N+2 サイズ：freq[x+1] を参照するため、番兵として余分に確保しています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    H = [next(it) for _ in range(N)]

    L = [-1] * N
    st = []
    for i in range(N):
        hi = H[i]
        while st and H[st[-1]] < hi:
            st.pop()
        L[i] = st[-1] if st else -1
        st.append(i)

    R = [-1] * N
    st = []
    for i in range(N - 1, -1, -1):
        hi = H[i]
        while st and H[st[-1]] < hi:
            st.pop()
        R[i] = st[-1] if st else -1
        st.append(i)

    freq = [0] * (N + 2)  # 1..N
    for i in range(N):
        lb = L[i] + 1 if L[i] != -1 else 0          # boundary index (0-based), or -1 -> use 0 in formula below
        rb = R[i] + 1 if R[i] != -1 else N + 1      # boundary index (1..N), or none -> N+1
        # Convert to 1-based boundary indices: left boundary = L[i]+1 (or 0), right boundary = R[i]+1 (or N+1)
        score = rb - lb - 1
        freq[score] += 1

    for x in range(N - 1, 0, -1):
        freq[x] += freq[x + 1]

    out = []
    for _ in range(Q):
        x = next(it)
        out.append(str(freq[x]))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。