Day 056-Q3 — 永続セグメント木（区間k番目・バージョン管理）

2026-06-09 赤色 Master / Phase 8+ ★★★★★★★★★ 永続データ構造 / 平衡BST / 座標圧縮

問題

整数列のバージョン管理と区間 $k$ 番目クエリを処理せよ。

  • S v i x: バージョン $v$ の $A_i$ を $x$ に変更した新バージョンを生成し番号を出力
  • Q v l r k: バージョン $v$ の $A[l..r]$ の $k$ 番目に小さい値を出力

制約

パラメータ範囲
$N$$1 \le N \le 10^5$
$Q$$1 \le Q \le 10^5$
$A_i, x$$1 \le A_i, x \le 10^9$
$k$$1 \le k \le r - l + 1$

入出力例

入力例 1

5 5
3 1 4 1 5
Q 0 1 5 3
S 0 3 2
Q 1 1 5 3
Q 0 2 4 2
S 1 1 10

出力例 1

3
1
4
2

バージョン0: [3,1,4,1,5]。全体の3番目に小さい値=3。
バージョン1 = v0の3番目を2に: [3,1,2,1,5]。3番目に小さい=4。

概念図: 永続セグメント木の構造

永続セグメント木: 更新でパスのみコピー（O(log N) ノード） バージョン0 root0 L0 R0 バージョン1（pos=3更新） root1 L0共有 R1 共有 新葉 凡例 新規生成ノード 共有ノード（変更なし） 更新1回でO(log N)ノード生成 区間 [l, r] の k 番目クエリ kth(roots[l], roots[r+1], 0, M, k): 左部分木のカウント差 lc を計算 k ≤ lc → 左へ潜る / k > lc → 右へ潜り k -= lc として進む

ヒント（段階的開示）

ヒント1: 方向性
永続セグメント木（値域でカウント）を使う。バージョン $v$ の prefix $[1, j]$ の永続セグ木根を保持し、差分で区間 $[l, r]$ の値分布を表現。$k$ 番目は左右分岐で $O(\log M)$。
ヒント2: アプローチ
  • 座標圧縮: 全値（更新値含む）を $[0, M)$ に圧縮
  • 永続セグ木: update(prev, pos) でパスを $O(\log M)$ ノードコピーして新根を返す
  • roots[j] = $A_0, \ldots, A_{j-1}$ 挿入後の根
  • 区間 $[l, r]$ の $k$ 番目 = kth(roots[l], roots[r+1], 0, M, k)
ヒント3: コード骨格 
def update(prev, lo, hi, pos):
    global nc
    cur = nc; nc += 1
    Lc[cur]=Lc[prev]; Rc[cur]=Rc[prev]; cnt[cur]=cnt[prev]+1
    if hi - lo == 1: return cur
    mid = (lo + hi) >> 1
    if pos < mid:
        Lc[cur] = update(Lc[prev], lo, mid, pos)
    else:
        Rc[cur] = update(Rc[prev], mid, hi, pos)
    return cur

def kth(u, v, lo, hi, k):
    if hi - lo == 1: return lo
    mid = (lo + hi) >> 1
    lc = cnt[Lc[v]] - cnt[Lc[u]]
    if k <= lc:
        return kth(Lc[u], Lc[v], lo, mid, k)
    return kth(Rc[u], Rc[v], mid, hi, k - lc)

模範解答 (Python)

import sys
from sys import setrecursionlimit
input = sys.stdin.readline
setrecursionlimit(500000)

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

    ops = []
    extra_vals = []
    for _ in range(Q):
        line = input().split()
        if line[0] == 'S':
            v, i, x = int(line[1]), int(line[2])-1, int(line[3])
            ops.append(('S', v, i, x))
            extra_vals.append(x)
        else:
            v, l, r, k = int(line[1]), int(line[2])-1, int(line[3])-1, int(line[4])
            ops.append(('Q', v, l, r, k))

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

    MAXNODE = (N + Q) * 20 + 10
    Lc = [0] * MAXNODE
    Rc = [0] * MAXNODE
    cnt = [0] * MAXNODE
    nc = 1

    def update(prev, lo, hi, pos):
        nonlocal nc
        cur = nc; nc += 1
        Lc[cur] = Lc[prev]; Rc[cur] = Rc[prev]; cnt[cur] = cnt[prev] + 1
        if hi - lo == 1:
            return cur
        mid = (lo + hi) >> 1
        if pos < mid:
            Lc[cur] = update(Lc[prev], lo, mid, pos)
        else:
            Rc[cur] = update(Rc[prev], mid, hi, pos)
        return cur

    def kth(u, v, lo, hi, k):
        if hi - lo == 1:
            return lo
        mid = (lo + hi) >> 1
        lc = cnt[Lc[v]] - cnt[Lc[u]]
        if k <= lc:
            return kth(Lc[u], Lc[v], lo, mid, k)
        return kth(Rc[u], Rc[v], mid, hi, k - lc)

    ver_arrays = [A[:]]
    ver_id = 0
    out = []

    for op in ops:
        if op[0] == 'S':
            _, v, i, x = op
            new_arr = ver_arrays[v][:]
            new_arr[i] = x
            ver_arrays.append(new_arr)
            ver_id += 1
            out.append(str(ver_id))
        else:
            _, v, l, r, k = op
            arr = ver_arrays[v]
            roots = [0] * (N + 1)
            for j in range(N):
                roots[j+1] = update(roots[j], 0, M, comp[arr[j]])
            idx = kth(roots[l], roots[r+1], 0, M, k)
            out.append(str(all_vals[idx]))

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

solve()

Step-by-Step 解説

Step 1: 座標圧縮

全バージョンで出現する値を収集し、$[0, M)$ に圧縮する。更新クエリの値も含めること。

Step 2: 永続セグメント木の更新

update(prev, lo, hi, pos) は根から葉までのパス上のノードをコピーして新根を返す。$O(\log M)$ ノードを生成。

Step 3: prefix 累積

roots[j+1] = update(roots[j], 0, M, comp[arr[j]]) で $j$ 番目の要素を追加した prefix セグ木を構築。

Step 4: k番目クエリ

2つの根 $u$（$[1, l)$ の累積）と $v$（$[1, r+1)$ の累積）の差分が区間 $[l, r]$ の値分布。左部分木のカウント差と $k$ を比較して二分決定。

計算量

処理計算量
prefix セグ木構築（1回）$O(N \log M)$
k番目クエリ$O(\log M)$
全体（簡略版）$O(Q \cdot N \log M)$（各 Q クエリで prefix 再構築）
最適版（永続点更新）$O((N + Q) \log M)$ 全体

よくあるミス

ミス原因正しい書き方
MAXNODE 不足挿入1回で $O(\log M)$ ノード(N + Q) * 20 程度で確保
kth の引数順$u$ と $v$ を逆にする$u$ = 小さい側（除外）、$v$ = 大きい側
更新値の圧縮漏れS クエリの $x$ を all_vals に含めない初期化時に全 $x$ を収集して圧縮

次のステップ

  • 永続 Treap による動的 insert/delete + k番目クエリ
  • HLD + 永続セグ木によるパス上 $k$ 番目クエリ

自己評価

自分の回答:

気づき・メモ: