問題
長さ $N$ の整数列 $A$ から Cartesian Tree を構築し、$Q$ 個の RMQ クエリ「$[l, r]$ の最小値のインデックス」に答えよ。
制約
$1 \le N, Q \le 5 \times 10^5$
$-10^9 \le A_i \le 10^9$（全て異なる）
入出力例
入力例 1
7 3
3 1 4 1 5 9 2
1 3
2 5
1 7出力例 1
2
4
2ヒント (段階的開示)
ヒント1: 方向性
Cartesian Tree は中順 = 元の列順、Min-Heap 性質。RMQ は LCA に対応するが、Sparse Table で $O(1)$ クエリでも十分。
ヒント2: アプローチ
単調スタックで $O(N)$ 構築。スタックは「右の子未確定ノード」を管理。新要素より大きいノードをポップ、それが新要素の左の子になる。
ヒント3: 誘導
Sparse Table:
sparse[k][i] = argmin(sparse[k-1][i], sparse[k-1][i + 2^(k-1)])。クエリは2区間の合成。模範解答 (Python)
import sys
import math
input = sys.stdin.readline
def main():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
parent = [0] * (N + 1)
left = [0] * (N + 1)
right = [0] * (N + 1)
stack = []
for i in range(1, N + 1):
last_popped = 0
while stack and A[stack[-1] - 1] > A[i - 1]:
last_popped = stack.pop()
if last_popped:
left[i] = last_popped
parent[last_popped] = i
if stack:
right[stack[-1]] = i
parent[i] = stack[-1]
stack.append(i)
LOG = max(1, int(math.log2(N)) + 1) if N > 0 else 1
sparse = [[0] * (N + 1) for _ in range(LOG + 1)]
for i in range(1, N + 1):
sparse[0][i] = i
for k in range(1, LOG + 1):
for i in range(1, N + 1):
j = i + (1 << (k - 1))
if j <= N:
si = sparse[k-1][i]
sj = sparse[k-1][j]
sparse[k][i] = si if A[si - 1] <= A[sj - 1] else sj
else:
sparse[k][i] = sparse[k-1][i]
log2 = [0] * (N + 1)
for i in range(2, N + 1):
log2[i] = log2[i // 2] + 1
results = []
for _ in range(Q):
l, r = map(int, input().split())
length = r - l + 1
k = log2[length]
li = sparse[k][l]
ri = sparse[k][r - (1 << k) + 1]
ans = li if A[li - 1] <= A[ri - 1] else ri
results.append(ans)
print('\n'.join(map(str, results)))
main()Step-by-Step 解説
1Cartesian Tree とは
中順 = 元の順、Heap 性質。区間最小値 = LCA。
中順 = 元の順、Heap 性質。区間最小値 = LCA。
2O(N) スタック構築
単調スタックでアモータイズド $O(N)$。各要素は1回 push/pop。
単調スタックでアモータイズド $O(N)$。各要素は1回 push/pop。
3Sparse Table
$O(N \log N)$ 前処理で $O(1)$ RMQ。重複2区間で min は同値。
$O(N \log N)$ 前処理で $O(1)$ RMQ。重複2区間で min は同値。
4計算量まとめ
Tree 構築 $O(N)$ + Sparse Table $O(N \log N)$ + クエリ $O(Q)$。
Tree 構築 $O(N)$ + Sparse Table $O(N \log N)$ + クエリ $O(Q)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 0/1-indexed の混同 | 変換忘れ | A[stack[-1] - 1] |
| Sparse Table 境界外 | j = i + 2^k > N | if j <= N で分岐 |
| log2 計算の精度 | math.log2(1) = 0.0 | log2 テーブル事前計算 |
次のステップ
- Farach-Colton: LCA を $O(1)$ で → RMQ $O(1)$ 化
- Treap（Cartesian Tree + ランダムキー）で平衡 BST