問題
長さ $N$ の数列 $A$ が与えられる。$Q$ 個のクエリ $(l,r)$ に対し、区間 $[l,r]$（1-indexed, 両端含む）の中央値（下側中央値、すなわち小さい方から $\lceil (r-l+1)/2\rceil$ 番目の値）を出力せよ。
入力形式
N Q
A_1 A_2 ... A_N
l_1 r_1
:
l_Q r_Q制約
$1 \le N \le 10^5$
$1 \le Q \le 10^5$
$1 \le A_i \le 10^9$
$1 \le l_i \le r_i \le N$
入出力例
入力例1
6 2
5 3 8 1 9 2
1 4
2 6出力例1
3
3区間$[1,4]$の値`5 3 8 1`→昇順`1 3 5 8`、長さ4なので2番目`3`。区間$[2,6]$の値`3 8 1 9 2`→昇順`1 2 3 8 9`、長さ5なので3番目`3`。
概念図
ヒント（段階的開示）
ヒント1: 方向性
「区間 $[l,r]$ の $k$ 番目に小さい値」を求める問題は、「値 $v$ 以下の要素が区間内にいくつあるか」を高速に数えられれば、その個数で二分探索することで求められる。区間内の要素を値でソートした状態で保持できるデータ構造を考えよ。
ヒント2: アプローチ
Merge Sort Treeを使う。セグメント木の各ノードに「その区間の要素をソートした配列」を持たせる。構築はマージソートと同じ要領で子2つのソート済み配列をマージ（$O(N\log N)$）。クエリでは区間 $[l,r]$ をカバーする $O(\log N)$ 個のノードで `bisect_right` により「$v$ 以下の個数」を合計する。この個数の単調性を利用し、全体の値集合上を二分探索すれば $k$ 番目の値が $O(\log^3 N)$ で求まる。
ヒント3: 誘導（コード骨格）
def count_le(l, r, v):
l += size; r += size
res = 0
while l < r:
if l & 1:
res += bisect_right(tree[l], v); l += 1
if r & 1:
r -= 1; res += bisect_right(tree[r], v)
l >>= 1; r >>= 1
return res`tree[1]`（ルート）は全要素の昇順配列になっているので、この配列上でインデックスを二分探索し `count_le(l,r,tree[1][mid]) >= k` を満たす最小のインデックスを探す。
模範解答 (Python)
import sys
import bisect
def solve():
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
size = 1
while size < n:
size *= 2
tree = [[] for _ in range(2 * size)]
for i in range(n):
tree[size + i] = [a[i]]
for i in range(size - 1, 0, -1):
tree[i] = sorted(tree[2 * i] + tree[2 * i + 1])
def count_le(l, r, v):
l += size
r += size + 1
res = 0
while l < r:
if l & 1:
res += bisect.bisect_right(tree[l], v)
l += 1
if r & 1:
r -= 1
res += bisect.bisect_right(tree[r], v)
l >>= 1
r >>= 1
return res
vals_sorted = tree[1]
out = []
for _ in range(q):
l = int(data[idx]) - 1; idx += 1
r = int(data[idx]) - 1; idx += 1
length = r - l + 1
k = (length + 1) // 2 # 下側中央値の順位（1-indexed）
lo, hi = 0, len(vals_sorted) - 1
while lo < hi:
mid = (lo + hi) // 2
if count_le(l, r, vals_sorted[mid]) >= k:
hi = mid
else:
lo = mid + 1
out.append(str(vals_sorted[lo]))
sys.stdout.write('\n'.join(out) + '\n')
solve()計算量: 構築 $O(N\log N)$。各クエリは値候補上の二分探索 $O(\log N)$ 回、各回で `count_le` が $O(\log^2 N)$、合計 $O(\log^3 N)$。全体で $O(N\log N + Q\log^3 N)$。
Step-by-Step 解説
1Merge Sort Tree の構築
葉には要素単体のリストを、内部ノードには左右の子をマージしたソート済みリストを格納する。
葉には要素単体のリストを、内部ノードには左右の子をマージしたソート済みリストを格納する。
2区間内「$v$ 以下の個数」クエリ
反復セグメント木の range query の要領で区間を $O(\log N)$ 個のノードに分解し、各ノードで `bisect_right` により個数を数え合計する。
反復セグメント木の range query の要領で区間を $O(\log N)$ 個のノードに分解し、各ノードで `bisect_right` により個数を数え合計する。
3値候補上の二分探索で $k$ 番目を特定
ルートノードの配列 `tree[1]` を「値の候補列」として使い、`count_le(l,r,候補値) >= k` を満たす最小の候補値を二分探索で求める。
ルートノードの配列 `tree[1]` を「値の候補列」として使い、`count_le(l,r,候補値) >= k` を満たす最小の候補値を二分探索で求める。
4中央値の順位の定義
長さ `length` の区間で下側中央値の順位は `k = (length + 1) // 2`。
長さ `length` の区間で下側中央値の順位は `k = (length + 1) // 2`。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 値の候補列を区間内の要素だけに限定してしまう | 二分探索対象を毎クエリ作り直そうとする | ルートノード `tree[1]`（全体の昇順配列）を候補列として使い回す |
| `bisect_left` と `bisect_right` を混同 | 「以下」と「未満」の境界の取り違え | 「$v$ 以下の個数」には `bisect_right` を使う |
| range query の半開区間変換で `r+1` を忘れる | 1-indexed→0-indexed→半開区間の変換ミス | `l += size; r += size + 1` として `[l,r)` にする |
| 中央値の順位を `length // 2` としてしまう | 「下側中央値」の定義を誤る | `k = (length + 1) // 2` で正しく計算する |
次のステップ
- 発展: Wavelet Tree / Wavelet Matrix を使えば同じクエリを $O(\log\sigma)$ に高速化できる
- 発展: 区間の分散や四分位範囲など複数の統計量を同時に求める拡張を考える
- 次回予告: 次回セッションでは Master Level の別テーマ（動的グラフ・多項式・幾何のいずれか）をローテーションで出題