まずは次の問題を考えます：

各 \(i\) について次の問題を解いてください：
区間 \([i,N]\) のうち、見える山の個数は？

この問題は、見えている山をスタックで管理しながら \(i\) の降順に考える、以下の擬似コードで表されるようなアルゴリズムにより \(O(N)\) で解くことができます。

stack = []  # indexを格納
ans = [0, ..., 0]  # 答えを格納
for i in N..1:
  while stack.size() > 0 and H[stack.top()] < H[i]:
    stack.pop()
  stack.push(i)
  ans[i] = stack.size()  

元の問題を考えます。クエリを先読みし、\(L\) ごとに分類しておきます。先程の問題を解く過程で、スタックが区間 \([L,N]\) の山を持っている状態になった時点を考えます。スタック内を二分探索することで、\(R\) までの山の個数を求めることができます。

スタックのサイズは \(O(N)\) であることから、質問クエリは 1 つあたり \(O(\log N)\) で処理することができ、全体で \(O(N+Q\log N)\) でこの問題を解くことができます。

実装例 (C++)

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

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

  vector<vector<array<int, 2>>> query(n);
  for(int i=0; i<q; i++){
    int l, r;
    cin >> l >> r;
    l--;
    query[l].push_back({r, i});
  }

  vector<int> ans(q);
  vector<int> st;

  for(int l=n-1; l>=0; l--){
    while(st.size() > 0 && h[st.back()] < h[l]){
      st.pop_back();
    }
    st.push_back(l);
    for(auto[r, i]: query[l]){
      auto it = upper_bound(st.begin(), st.end(), r, greater<int>());
      ans[i] = st.end() - it;
    }
  }

  for(int i=0; i<q; i++){
    cout << ans[i] << endl;
  }
}

実装例 (Python)

import bisect
N, Q = map(int, input().split())
H = list(map(int, input().split()))
query = [[] for _ in range(N)]
for i in range(Q):
  L, R = map(int, input().split())
  L -= 1
  query[L].append((R, i))

ans = [0] * Q
stack = []
for L in range(N-1, -1, -1):
  while len(stack) and H[stack[-1]] < H[L]:
    stack.pop()
  stack.append(L)
  for R, i in query[L]:
    ans[i] = len(stack) - bisect.bisect_right(stack, -R, key=lambda x:-x)

print(*ans)

この他、ダブリングを用いた解法もありますが、そちらはAIによる解説に譲ります。