概要

各クエリ区間 \([L,R]\) を左から見たときに「それまでの最高標高を更新（同値含む）した山」の個数（= 見える山の個数）を、高速に求めます。

考察

「見える」の言い換え

山 \(k\) が見える条件は「左側に自分より厳密に高い山がない」なので、区間 \([L,R]\) を左から走査したとき

• その時点までの最大値を \(M\) とすると
• \(H_k \ge M\) のときだけ見える（同じ高さも見える）

つまり、見える山は「区間の prefix 最大値列（同値を許す）」に対応します。

素朴解の問題点

各クエリごとに \(L\) から \(R\) まで順に最大値を更新しながら数えると \(O(R-L+1)\)。 最悪で \(O(NQ)\) となり、\(N,Q \le 2\times 10^5\) では間に合いません。

重要な観察：最大値は「次により高い山」によってのみ更新される

位置 \(i\) にいるとき、現在の最大値が \(H_i\) だとすると、次に最大値が更新されるのは 「\(i\) より右で初めて \(H_i\) より厳密に高い山」に到達したときです。

そこで各 \(i\) について

• \(\mathrm{nge}[i]\) = 右側で最初に \(H_{\mathrm{nge}[i]} > H_i\) となる位置（無ければ番兵 \(N+1\)）

を考えると、区間 \([i,\,\mathrm{nge}[i)-1]\) の間は最大値が \(H_i\) のままです。

この区間内で見えるのは「高さがちょうど \(H_i\) の山」だけです（それより低い山は最大値に負けて見えない）。 よって

• \(w[i]\) = 区間 \([i,\,\mathrm{nge}[i)-1]\) に含まれる「高さ \(H_i\) の山」の個数

が分かれば、クエリは - \(i=L\) から始めて \(\mathrm{nge}\) をたどりながら \(w\) を足す という形になります（ただし最後は区間が途中で切れるので別処理）。

アルゴリズム

1. \(\mathrm{nge}\)（次の「より高い」要素）を単調スタックで作る

右から左へ走査し、スタックには「右側にある山のうち、高さが単調増加になるように」候補を保持します。

• 今見ている \(H_i\) 以下の山は、\(i\) から見た「次のより高い山」にはなり得ないので pop
• 残った先頭が \(\mathrm{nge}[i]\)（無ければ \(N+1\)）

これで全体 \(O(N)\) で作れます。

2. \(w[i]\) を「同じ高さの出現位置リスト」で数える

各標高 \(h\) について、その出現位置を昇順に並べた配列 \(\text{pos}[h]\) を持ちます。

位置 \(i\) の高さを \(h=H_i\)、区間端を \(end=\mathrm{nge}[i]-1\) とすると - \(w[i]\) = \(\text{pos}[h]\) のうち \([i,end]\) に入る個数

これは二分探索で求まります。 実装では - rank[i] = \(\text{pos}[H_i]\) 内での \(i\) の添字（0-index） を持っておき、 - bisect_right(pos[h], end) - rank[i] で \([i,end]\) の個数を一発で出しています。

3. \(\mathrm{nge}\) でのジャンプをダブリング（二分累乗）で高速化

\(\mathrm{nge}\) は「次のより高い山」へのポインタなので、そこを何回もたどるとクエリが遅くなります。 そこでダブリングを作ります：

• up[k][i] = \(\mathrm{nge}\) を \(2^k\) 回たどった先
• sw[k][i] = その間に足される \(w\) の総和

遷移は - up[k][i] = up[k-1][ up[k-1][i] ] - sw[k][i] = sw[k-1][i] + sw[k-1][ up[k-1][i] ]

で構築します。

4. クエリ処理

クエリ \([L,R]\) に対して、区間が完全に含まれる「まとまり」だけをダブリングで飛びます。

• いま cur にいるとき、cur のまとまりは \([cur,\mathrm{nge}[cur)-1]\)
• このまとまりが完全に \(R\) 以内に収まる条件は \(\mathrm{nge}[cur] \le R+1\)

よって limit = R+1 として、 大きい \(k\) から順に up[k][cur] <= limit なら - res += sw[k][cur] - cur = up[k][cur] と更新します。

最後に残った cur については、まとまりが途中で切れる可能性があるので - 高さ \(H[cur]\) の山が \([cur,R]\) にいくつあるか を同じく二分探索で足して終わりです。

計算量

• 時間計算量:
  
  • \(\mathrm{nge}\) 構築 \(O(N)\)
    
  • \(w[i]\) 計算（各 \(i\) で二分探索） \(O(N\log N)\)
    
  • ダブリング構築 \(O(N\log N)\)
    
  • 各クエリ \(O(\log N)\)
    よって全体で \(O\big((N+Q)\log N\big)\)
• 空間計算量: \(O(N\log N)\)（ダブリング表）

実装のポイント

• 「見えない条件」が 厳密に高い（\(>\)）なので、同じ高さは遮られず両方見える点が重要です。
  そのため \(\mathrm{nge}\) は「次の *strictly greater*」として <= を pop しています。

• クエリで「まとまりが完全に入る」判定は nge[cur] <= R+1（= nge[cur]-1 <= R）です。

• Python で \(N\log N\) の配列を持つので、メモリ削減のため array('I') を使っています。

• 入力も高速化のため sys.stdin.buffer.read() からの手書きパーサを使っています。

  ソースコード

import sys
from bisect import bisect_right
from array import array

data = sys.stdin.buffer.read()
m = len(data)
p = 0

def ni():
    global p
    while p < m and data[p] <= 32:
        p += 1
    x = 0
    while p < m and data[p] > 32:
        x = x * 10 + (data[p] - 48)
        p += 1
    return x

N = ni()
Q = ni()

H = [0] * (N + 2)
pos = {}
rank = [0] * (N + 2)

for i in range(1, N + 1):
    h = ni()
    H[i] = h
    lst = pos.get(h)
    if lst is None:
        pos[h] = [i]
        rank[i] = 0
    else:
        rank[i] = len(lst)
        lst.append(i)

# Next strictly greater element to the right
nge = [0] * (N + 2)
stack = []
for i in range(N, 0, -1):
    hi = H[i]
    while stack and H[stack[-1]] <= hi:
        stack.pop()
    nge[i] = stack[-1] if stack else N + 1
    stack.append(i)
nge[N + 1] = N + 1

# Weight: number of indices t in [i, nge[i)-1] with H[t] == H[i]
w = [0] * (N + 2)
br = bisect_right
for i in range(1, N + 1):
    end = nge[i] - 1
    lst = pos[H[i]]
    w[i] = br(lst, end) - rank[i]
w[N + 1] = 0

LOG = (N + 2).bit_length()
up = [array('I', [0]) * (N + 2) for _ in range(LOG)]
sw = [array('I', [0]) * (N + 2) for _ in range(LOG)]

up0 = up[0]
sw0 = sw[0]
for i in range(1, N + 2):
    up0[i] = nge[i]
    sw0[i] = w[i]

for k in range(1, LOG):
    up_prev = up[k - 1]
    sw_prev = sw[k - 1]
    up_k = up[k]
    sw_k = sw[k]
    for i in range(1, N + 2):
        mid = up_prev[i]
        up_k[i] = up_prev[mid]
        sw_k[i] = sw_prev[i] + sw_prev[mid]

ks = list(range(LOG - 1, -1, -1))
out = []
for _ in range(Q):
    L = ni()
    R = ni()
    limit = R + 1

    cur = L
    res = 0
    for k in ks:
        nxt = up[k][cur]
        if nxt <= limit:
            res += sw[k][cur]
            cur = nxt

    if cur <= R:
        h = H[cur]
        res += br(pos[h], R) - rank[cur]

    out.append(str(res))

sys.stdout.write("\n".join(out))

---

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