問題
$N$ 本の棒からなるヒストグラムが与えられる。$i$ 番目の棒の高さは $H_i$ である。$Q$ 個のクエリに答えよ。各クエリは $(l, r)$ で、区間 $[l, r]$ 内のヒストグラムにおける最大矩形面積を求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 2 \times 10^5$ |
| $Q$ | $1 \le Q \le 2 \times 10^5$ |
| $H_i$ | $1 \le H_i \le 10^9$ |
| $l, r$ | $0 \le l \le r < N$（0-indexed） |
入出力例
入力例 1
6 3
2 1 5 6 2 3
0 5
2 4
3 5出力例 1
10
10
6全体[2,1,5,6,2,3]→高さ2×幅5=10。[5,6,2]→5×2=10。[6,2,3]→2×3=6。
概念図: Cartesian Tree + 分割統治による最大矩形
ヒント（段階的開示）
ヒント1: 方向性
Sparse Table で区間最小インデックスを $O(1)$ で取得し、分割統治で最大矩形を求める。各クエリは区間最小で分割 → 3候補の最大値。
ヒント2: アプローチ
クエリ $(l, r)$ に対して:
- 区間 $[l, r]$ の最小値インデックス $m$ を $O(1)$ で取得（Sparse Table）
- $H[m] \times (r - l + 1)$（全域を $H[m]$ で押す矩形）
- $\text{solve}(l, m-1)$ と $\text{solve}(m+1, r)$ の再帰解
- 3つの最大値を返す
ヒント3: コード骨格
def solve(l, r):
if l > r: return 0
if l == r: return H[l]
m = rmq(l, r) # 最小値のインデックス
return max(
H[m] * (r - l + 1),
solve(l, m - 1),
solve(m + 1, r)
)模範解答 (Python)
import sys
from math import log2
input = sys.stdin.readline
def main():
N, Q = map(int, input().split())
H = list(map(int, input().split()))
LOG = max(1, int(log2(N)) + 1) if N > 0 else 1
sparse = [[i] * N for _ in range(LOG)]
for j in range(1, LOG):
for i in range(N - (1 << j) + 1):
a, b = sparse[j-1][i], sparse[j-1][i + (1 << (j-1))]
sparse[j][i] = a if H[a] <= H[b] else b
def rmq(l, r):
if l > r: return l
k = int(log2(r - l + 1))
a, b = sparse[k][l], sparse[k][r - (1 << k) + 1]
return a if H[a] <= H[b] else b
sys.setrecursionlimit(400010)
def solve(l, r):
if l > r: return 0
if l == r: return H[l]
m = rmq(l, r)
full = H[m] * (r - l + 1)
left = solve(l, m - 1)
right = solve(m + 1, r)
return max(full, left, right)
out = []
for _ in range(Q):
l, r = map(int, input().split())
out.append(solve(l, r))
print('\n'.join(map(str, out)))
main()Step-by-Step 解説
Step 1: Sparse Table 構築
区間最小インデックスを $O(N \log N)$ 前処理、$O(1)$ クエリで構築する。
Step 2: 分割統治
クエリ区間 $[l, r]$ の最小値インデックス $m$ を取り、3候補の最大値を返す: (1) $H[m] \times (r - l + 1)$、(2) solve(l, m-1)、(3) solve(m+1, r)。
Step 3: 計算量
| 処理 | 計算量 |
|---|---|
| Sparse Table 前処理 | $O(N \log N)$ |
| solve 1クエリ（期待値） | $O(N)$ 最悪 |
| Qクエリ全体 | $O(Q \cdot N)$ 最悪 |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| l > r での再帰停止漏れ | 空区間のベースケース欠落 | if l > r: return 0 |
| Sparse Table のインデックス越え | r - (1 << k) + 1 < l になりうる | k を int(log2(r-l+1)) で計算 |
| 再帰深度超過 | N=2×10^5 で連鎖再帰 | sys.setrecursionlimit を設定 |
次のステップ
発展: 永続 Cartesian Tree でクエリ $O(\log N)$ に改善。関連: Segment Tree でヒストグラム最大矩形を区間マージ（モノイド）で $O(\log N)$ クエリ。