まず各ビルに対して見晴らしスコアを求めます。

俗に単調スタックと呼ばれる、単調減少列を管理するスタックを用いることで \(O(N)\) で全ての \(L_i\) を求めることができます。その解法の説明は他に任せ、ここでは ACL (AtCoder Library) を前提とし、セグメントツリーを用いて実装を省力でやる解法を説明します。

区間最大値を取得できるセグメントツリーにビルの高さを乗せることを考えます。このとき、各 \(i\) について min_left メソッドにより \(L_i\) を \(O(\log N)\) で求めることができます。 \(R_i\) も同様に max_right を用いて求めることができます。

質問に答える部分は二分探索により高速に行えます。よって \(O(N\log N+Q\log N)\) でこの問題を解くことができました。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/segtree>
using namespace std;

int op(int x, int y){return max(x, y);}
int e(){return 0;}

int main(){
  int n, q;
  cin >> n >> q;
  vector<int>h(n);
  for(int i=0; i<n; i++) cin >> h[i];

  atcoder::segtree<int, op, e>seg(h);
  vector<int>ans;
  for(int i=0; i<n; i++){
    int r=seg.max_right(i, [&](int x){return x <= h[i];});
    int l=seg.min_left(i, [&](int x){return x <= h[i];});
    ans.push_back(r-l);
  }
  sort(ans.begin(), ans.end());

  for(int i=0; i<q; i++){
    int x;
    cin >> x;
    cout << (ans.end() - lower_bound(ans.begin(), ans.end(), x)) << endl;
  }
}

実装例 (Python)

from bisect import bisect_left
from atcoder.segtree import SegTree
N, Q = map(int, input().split())
H = list(map(int,input().split()))

seg = SegTree(max,0,H)
ans = []
for i in range(N):
  r = seg.max_right(i, lambda x: x <= H[i])
  l = seg.min_left(i, lambda x: x <= H[i])
  ans.append(r-l)
ans.sort()

for _ in range(Q):
  X = int(input())
  print(N - bisect_left(ans, X))