問題
長さ $N$ の数列 $a_1, a_2, \dots, a_N$ が与えられる。$Q$ 個のクエリ l r k について、区間 $[l, r]$ に含まれる値のうち $k$ 番目に小さい値 を出力せよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N, Q$ | $1 \le N, Q \le 2\times10^5$ | 要素数・クエリ数 |
| $a_i$ | $1 \le a_i \le 10^9$ | 要素の値（座標圧縮対象） |
| $l, r, k$ | $1 \le l \le r \le N,\ 1 \le k \le r-l+1$ | 区間と順位 |
入出力例
入力例1
5 3
1 5 2 3 4
1 5 3
2 4 1
3 5 2出力例1
3
2
3$[1,5]$ ソートで3番目=3。$[2,4]=(5,2,3)$ の1番目=2。$[3,5]=(2,3,4)$ の2番目=3。
概念図
ヒント
ヒント1（方向性）
「区間の $k$ 番目」は値でソートした累積個数の二分探索。接頭辞 $[1,i]$ の「値の出現頻度」を持てば、区間 $[l,r]$ の頻度は差分で得られる。
ヒント2（アプローチ）
値域を座標圧縮し、接頭辞ごとに頻度セグメント木を作る。$N$ 本独立ではメモリ $O(N^2)$。永続化で前版とノード共有すれば更新1回 $O(\log N)$ ノード。
ヒント3（ほぼ答え）
while lo < hi:
leftcnt = cnt[lc[v]] - cnt[lc[u]]
if k <= leftcnt:
u, v, hi = lc[u], lc[v], mid
else:
k -= leftcnt
u, v, lo = rc[u], rc[v], mid + 1模範解答
import sys
def main():
data = sys.stdin.buffer.read().split()
idx = 0
n = int(data[idx]); idx += 1
q = int(data[idx]); idx += 1
a = [int(data[idx + i]) for i in range(n)]; idx += n
xs = sorted(set(a))
comp = {v: i for i, v in enumerate(xs)}
m = len(xs)
MAXN = n * 20 + 10
lc = [0] * MAXN
rc = [0] * MAXN
cnt = [0] * MAXN
cur = 0 # node 0 = 空ノード（共有）
roots = [0] * (n + 1)
def update(prev, lo, hi, pos):
nonlocal cur
cur += 1
node = cur
lc[node] = lc[prev]; rc[node] = rc[prev]; cnt[node] = cnt[prev] + 1
if lo == hi:
return node
mid = (lo + hi) // 2
if pos <= mid:
lc[node] = update(lc[prev], lo, mid, pos)
else:
rc[node] = update(rc[prev], mid + 1, hi, pos)
return node
for i in range(1, n + 1):
roots[i] = update(roots[i - 1], 0, m - 1, comp[a[i - 1]])
out = []
for _ in range(q):
l = int(data[idx]); r = int(data[idx + 1]); k = int(data[idx + 2]); idx += 3
u = roots[l - 1]; v = roots[r]
lo, hi = 0, m - 1
while lo < hi:
mid = (lo + hi) // 2
leftcnt = cnt[lc[v]] - cnt[lc[u]]
if k <= leftcnt:
u, v, hi = lc[u], lc[v], mid
else:
k -= leftcnt; u, v, lo = rc[u], rc[v], mid + 1
out.append(str(xs[lo]))
sys.stdout.write('\n'.join(out) + '\n')
main()計算量: 構築 $O(N\log N)$、各クエリ $O(\log N)$、合計 $O((N+Q)\log N)$。
Step-by-Step 解説
Step 1: 座標圧縮
値は最大 $10^9$ だが種類は高々 $N$。sorted(set(a)) で圧縮し、葉をランクに対応させる。
Step 2: 永続更新でノード共有
変更しない側の子は前版のノードをそのまま指す。1回の挿入で作る新ノードは根から葉までの $O(\log N)$ 個だけ。
Step 3: 版の差分で区間頻度
| 量 | 意味 |
|---|---|
cnt[lc[v]] - cnt[lc[u]] | 区間 $[l,r]$ の左部分木側の要素数 |
v = root[r], u = root[l-1] | 接頭辞頻度木の2版 |
Step 4: 木上の二分探索でk番目
左の個数 leftcnt が $k$ 以上なら左、そうでなければ $k$ から引いて右へ。葉に着いたランクを値に戻す。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| メモリ不足 (MLE) | ノード配列が小さい | MAXN = N*(⌈log₂M⌉+2) 程度 |
| 空ノードの破壊 | node 0 を更新 | node 0 は cnt=lc=rc=0 の共有ダミー固定 |
| 区間を root[l]〜root[r] にする | 差分がずれる | 正しくは root[l-1] と root[r] |
| k を 0-indexed で処理 | 1個ずれる | $k$ は1始まり、k <= leftcnt |
次のステップ
- 発展: 区間内で $x$ 以下の値の個数、区間中央値、区間相異なる値
- 発展: オフラインなら Merge Sort Tree / Wavelet Matrix でも解ける（比較）
- 次回予告: Hopcroft-Karp（最大二部マッチング）
自己評価
理解度: / /
自分の回答:
気づき・メモ: