Day 036-Q2 | Merge Sort Tree — 区間k番目クエリ

問題

長さ $N$ の整数列 $A$ と $Q$ 個のクエリが与えられる。各クエリは $(l, r, k)$ の形で，$A[l..r]$ の中で $k$ 番目に小さい値を求めよ。静的配列（更新なし）とする。

制約

$1 \le N, Q \le 2 \times 10^5$

$1 \le A_i \le 10^9$

$1 \le l \le r \le N$

$1 \le k \le r - l + 1$

入出力例

入力例 1

7 3
3 1 4 1 5 9 2
1 7 3
2 5 2
3 7 4

出力例 1

3
3
9

A[1..7] ソート済み = [1,1,2,3,4,5,9]，3番目 = 3
A[2..5] ソート済み = [1,3,4,5]，2番目 = 3
A[3..7] ソート済み = [2,4,5,9,4]→[2,4,4,5,9]，4番目 = 9

概念図: Merge Sort Tree

セグメント木の各ノードに対応区間のソート済み配列を持つ。クエリは「値 $x$ 以下の個数」を二分探索。

ヒント (段階的開示)

ヒント1: 方向性

区間 k 番目は「値 $x$ 以下が $k$ 個以上」となる最小 $x$ を二分探索することで求まる。「値 $x$ 以下の個数」を効率よく求める構造が必要。

ヒント2: Merge Sort Tree

セグメント木の各ノードに対応区間のソート済み配列を持つ。 count_le(ql, qr, x): $O(\log N)$ 個のノードそれぞれで bisect_right → $O(\log^2 N)$。

ヒント3: 座標圧縮 + 二分探索

# 座標圧縮
sorted_vals = sorted(set(A))
comp = {v:i for i,v in enumerate(sorted_vals)}

# k番目クエリ
lo, hi = 0, M-1
while lo < hi:
    mid = (lo+hi)//2
    if count_le(1, 0, N-1, l, r, mid) >= k:
        hi = mid
    else:
        lo = mid+1
return sorted_vals[lo]

模範解答 (Python)

import sys
import bisect
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    sorted_vals = sorted(set(A))
    comp = {v: i for i, v in enumerate(sorted_vals)}
    M = len(sorted_vals)

    tree = [[] for _ in range(4 * N)]

    def build(node, l, r):
        if l == r:
            tree[node] = [comp[A[l]]]
            return
        mid = (l + r) // 2
        build(2*node, l, mid)
        build(2*node+1, mid+1, r)
        i, j = 0, 0
        la, lb = tree[2*node], tree[2*node+1]
        merged = []
        while i < len(la) and j < len(lb):
            if la[i] <= lb[j]:
                merged.append(la[i]); i += 1
            else:
                merged.append(lb[j]); j += 1
        merged.extend(la[i:]); merged.extend(lb[j:])
        tree[node] = merged

    build(1, 0, N - 1)

    def count_le(node, l, r, ql, qr, x):
        if qr < l or r < ql: return 0
        if ql <= l and r <= qr:
            return bisect.bisect_right(tree[node], x)
        mid = (l + r) // 2
        return (count_le(2*node, l, mid, ql, qr, x)
              + count_le(2*node+1, mid+1, r, ql, qr, x))

    out = []
    for _ in range(Q):
        l, r, k = map(int, input().split())
        l -= 1; r -= 1
        lo, hi = 0, M - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if count_le(1, 0, N-1, l, r, mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        out.append(str(sorted_vals[lo]))

    print('\n'.join(out))

solve()

Step-by-Step 解説

1座標圧縮
$A_i$ の値域が広いため，値を $[0, M)$ に圧縮する。$M \le N$。

2Merge Sort Tree 構築
セグメント木の各ノードに対応区間のソート済み（圧縮済み）値リストを持つ。構築: $O(N \log N)$ 時間・空間。

3count_le クエリ
区間 $[ql, qr]$ で圧縮値 $\le x$ の個数を bisect_right でカウント。$O(\log^2 N)$ per query。

4k 番目クエリ
圧縮値を二分探索。count_le(..., mid) ≥ k となる最小 mid が答え。合計 $O(\log^3 N)$ per query。

計算量

構築: $O(N \log N)$ 時間・空間
count_le: $O(\log^2 N)$ per query
k番目クエリ: $O(\log^3 N)$ per query
合計: $O(N \log N + Q \log^3 N)$

よくあるミス

ミス	原因	正しい書き方
マージ時に非ソート	build後のマージが wrong	正しくマージ実装（or sorted()）
座標圧縮後の復元忘れ	`lo` を出力	`sorted_vals[lo]` を出力
0-indexed/1-indexed ずれ	ql,qrのずれ	`l-=1; r-=1` で変換
bisect_right vs bisect_left	境界条件	等しい場合を含めるので `bisect_right`

次のステップ

発展: Wavelet Tree による $O(N \log N)$ 構築・$O(\log N)$ クエリへの改善
応用: 更新あり（動的）の場合は BIT of BIT や平衡 BST を使用

自己評価

完全理解おおむね理解要復習

Day 036-Q2 — Merge Sort Tree — 区間 k 番目クエリ

問題

制約