概要

各ビルについて、左右それぞれで最も近い「自分より高いビル」を見つけ、その間の区間の長さを「見晴らしスコア」として計算し、クエリごとにスコアが \(X_k\) 以上のビルの棟数を答える問題です。

考察

重要な気づき：Next Greater Element（次に大きい要素）

各ビル \(i\) に対して求めたい \(R_i\)（右側で最も近い、自分より高いビル）と \(L_i\)（左側で最も近い、自分より高いビル）は、競技プログラミングでよく知られた Next Greater Element (NGE) 問題そのものです。

素朴なアプローチの問題点

各ビルに対して愚直に左右を走査すると、1つのビルあたり最悪 \(O(N)\) かかり、全体で \(O(N^2)\) となります。\(N \leq 2 \times 10^5\) では TLE になります。

解決策：単調スタック

単調スタック（Monotonic Stack） を使えば、すべてのビルの \(R_i\) と \(L_i\) をそれぞれ \(O(N)\) で求められます。

クエリへの対応

\(Q\) 個のクエリそれぞれに対して全スコアを走査すると \(O(NQ)\) で TLE の恐れがあります。事前にスコアの 接尾辞和（suffix sum） を計算しておけば、各クエリに \(O(1)\) で答えられます。

アルゴリズム

ステップ1：\(R_i\) の計算（右方向の Next Greater Element）

配列を左から右へ走査しながら、単調スタック（スタック内の要素の高さが単調減少になるように管理）を用います。

• ビル \(i\) を処理するとき、スタックの先頭にあるビル \(j\) の高さが \(H[i]\) より小さければ、ビル \(j\) にとっての「右側で最も近い、より高いビル」は \(i\) です。スタックから \(j\) を取り出し \(R_j = i\) とします。
• これを条件を満たす限り繰り返し、最後に \(i\) をスタックに積みます。

具体例（\(H = [3, 1, 4, 1, 5]\)）： - ビル0（高さ3）：スタック空 → push。スタック=[0] - ビル1（高さ1）：\(H[0]=3 > 1\) なので pop しない → push。スタック=[0,1] - ビル2（高さ4）：\(H[1]=1 < 4\) → \(R_1 = 2\)。\(H[0]=3 < 4\) → \(R_0 = 2\)。push。スタック=[2] - ビル3（高さ1）：pop しない → push。スタック=[2,3] - ビル4（高さ5）：\(H[3]=1 < 5\) → \(R_3 = 4\)。\(H[2]=4 < 5\) → \(R_2 = 4\)。push。スタック=[4] - スタックに残ったビル4は \(R_4\) が存在しない。

ステップ2：\(L_i\) の計算（左方向の Next Greater Element）

配列を右から左へ走査し、同様の単調スタックを使います。ビル \(i\) を処理するとき、スタック先頭のビル \(j\)（\(j > i\)）の高さが \(H[i]\) より小さければ \(L_j = i\) とします。

ステップ3：見晴らしスコアの計算

0-indexed で管理する場合、問題文の 1-indexed の式を変換します。

条件	1-indexed の式	0-indexed での式
\(L_i, R_i\) 両方存在	\(R_i - L_i - 1\)	\(ri - li - 1\)
\(R_i\) のみ存在	\(R_i - 1\)	\(ri\)
\(L_i\) のみ存在	\(N - L_i\)	\(N - li - 1\)
どちらも存在しない	\(N\)	\(N\)

ステップ4：クエリへの回答

1. 配列 \(\text{count}[s]\)（スコアが \(s\) のビルの棟数）を作る。
2. 後ろから累積和を取り、\(\text{suffix\_count}[x] = \sum_{s=x}^{N} \text{count}[s]\)（スコアが \(x\) 以上のビルの棟数）を計算。
3. 各クエリ \(X_k\) に対し \(\text{suffix\_count}[X_k]\) を出力。

計算量

• 時間計算量: \(O(N + Q)\)
  • 単調スタックによる \(R_i, L_i\) の計算がそれぞれ \(O(N)\)
  • スコア計算が \(O(N)\)
  • 接尾辞和の構築が \(O(N)\)
  • 各クエリへの回答が \(O(1) \times Q\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

• 0-indexed と 1-indexed の変換に注意：問題文は 1-indexed で定義されていますが、コード内では 0-indexed で処理するため、スコア計算式の変換を正確に行う必要があります。

• 単調スタックの方向：\(R_i\) は左→右、\(L_i\) は右→左に走査します。どちらも「スタック内の要素より大きい値が来たら pop して記録」という同じ原理です。

• 接尾辞和で前処理：クエリごとに線形探索を避けるため、スコアの分布を先に集計し接尾辞和を作ることで、各クエリ \(O(1)\) に高速化します。

  ソースコード

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    H = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    queries = [int(input_data[idx + i]) for i in range(Q)]
    idx += Q
    
    # Find R_i (next greater element to the right) using monotonic stack
    R = [0] * N  # 0-indexed, store 1-indexed or use sentinel
    # We'll use 1-indexed positions internally
    # R[i] = index (1-indexed) of next greater to the right, or -1 if none
    stack = []
    R_val = [-1] * N
    for i in range(N):
        while stack and H[stack[-1]] < H[i]:
            R_val[stack.pop()] = i  # 0-indexed
        stack.append(i)
    
    # Find L_i (next greater element to the left) using monotonic stack
    L_val = [-1] * N
    stack = []
    for i in range(N - 1, -1, -1):
        while stack and H[stack[-1]] < H[i]:
            L_val[stack.pop()] = i  # 0-indexed
        stack.append(i)
    
    # Compute scores
    # Convert to 1-indexed for the formula
    scores = [0] * N
    for i in range(N):
        li = L_val[i]  # 0-indexed or -1
        ri = R_val[i]  # 0-indexed or -1
        
        has_L = (li != -1)
        has_R = (ri != -1)
        
        if has_L and has_R:
            # 1-indexed: R_i - L_i - 1
            # In 0-indexed: (ri+1) - (li+1) - 1 = ri - li - 1
            scores[i] = ri - li - 1
        elif has_R and not has_L:
            # 1-indexed: R_i - 1
            # In 0-indexed: (ri+1) - 1 = ri
            scores[i] = ri
        elif has_L and not has_R:
            # 1-indexed: N - L_i
            # In 0-indexed: N - (li+1) = N - li - 1
            scores[i] = N - li - 1
        else:
            scores[i] = N
    
    # Build suffix count: for each score value, count how many buildings have score >= X
    # Create count array
    count = [0] * (N + 2)
    for s in scores:
        if 1 <= s <= N:
            count[s] += 1
    
    # suffix_count[x] = number of buildings with score >= x
    suffix_count = [0] * (N + 2)
    for x in range(N, 0, -1):
        suffix_count[x] = suffix_count[x + 1] + count[x]
    
    out = []
    for k in range(Q):
        x = queries[k]
        out.append(str(suffix_count[x]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。