問題
$N$ 個の整数列 $A$、$Q$ 個のクエリ l r k に対して、$A[l..r]$ の中で $k$ 番目に小さい値を求めよ。
制約
$1 \le N \le 10^5$
$1 \le Q \le 10^5$
$1 \le l \le r \le N$
$1 \le k \le r-l+1$
入出力例
入力例 1
7 3
3 1 4 1 5 9 2
2 5 2
1 7 3
3 6 1出力例 1
1
3
1ヒント (段階的開示)
ヒント1: 方向性
Mo's Algorithm + 乱択、または Persistent Segment Tree。ここでは Randomized Quickselect。
ヒント2: アプローチ
乱択ピボットで分割して再帰的に絞り込む。期待計算量 $O(N)$。
ヒント3: 誘導
lo/mid/hi の3分割で重複要素を正しく扱う。
模範解答 (Python)
import sys
import random
input = sys.stdin.readline
sys.setrecursionlimit(500000)
def quickselect(arr, k):
if len(arr) == 1:
return arr[0]
pivot = random.choice(arr)
lo = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
hi = [x for x in arr if x > pivot]
if k <= len(lo):
return quickselect(lo, k)
elif k <= len(lo) + len(mid):
return pivot
else:
return quickselect(hi, k - len(lo) - len(mid))
def solve():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
results = []
for _ in range(Q):
l, r, k = map(int, input().split())
sub = A[l-1:r]
results.append(quickselect(sub, k))
print('\n'.join(map(str, results)))
solve()Step-by-Step 解説
1乱択の意義
決定論的だと最悪 $O(N^2)$。
決定論的だと最悪 $O(N^2)$。
random.choice で期待値 $O(N)$ に収まる。
2三分割
lo / mid / hi で重複要素を正しく扱う。
lo / mid / hi で重複要素を正しく扱う。
3計算量
各クエリ期待 $O(r-l+1)$。$Q$ が多いと Persistent Segment Tree が最適。
各クエリ期待 $O(r-l+1)$。$Q$ が多いと Persistent Segment Tree が最適。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| ピボット固定（先頭/末尾） | ソート済み入力で $O(N^2)$ | random.choice(arr) |
| mid を考慮しない | 重複要素でバグ | lo/mid/hi の3分割 |
| $k$ の補正忘れ | hi 再帰時にそのまま | k - len(lo) - len(mid) |
次のステップ
- 発展問題: Persistent Segment Tree + 座標圧縮で $O(N \log N + Q \log N)$
- 応用: Introselect（最悪 $O(N)$ 保証）