Day 107-Q3 | Fractional Cascading（複数ソート済み配列の一括探索）

問題

$k$個の昇順ソート済み配列 $L_1,L_2,\dots,L_k$ が与えられる。$Q$個のクエリ値 $x_1,\dots,x_Q$ のそれぞれについて、すべての $L_i$ に対して「$x_j$以上で最小の要素」（存在しなければ-1）を出力せよ。

配列ごとに毎回二分探索すると$O(k\log N)$かかる。Fractional Cascadingを使うと、最初の1本だけ二分探索し、残り$k-1$本は前の結果から$O(1)$で辿れるようになり、1クエリあたり$O(\log N + k)$に改善できる。

入力形式

k
n_1
a_{1,1} ... a_{1,n_1}
...
n_k
a_{k,1} ... a_{k,n_k}
Q
x_1
...
x_Q

制約

$1 \le k \le 8$

$\sum n_i \le 2\times10^5$

$1 \le Q \le 10^5$

$0 \le a_{i,j}, x_j \le 10^9$

入出力例

入力例1

3
5
2 5 9 14 20
4
1 8 8 30
3
3 3 25
3
10
0
26

出力例1

14 30 25
2 1 3
-1 30 -1

各クエリ行は$L_1,L_2,L_3$それぞれに対するsuccessorを空白区切りで出力する。$x=10$: 14,30,25。$x=0$: 2,1,3。$x=26$: $L_1,L_3$は無く-1、$L_2$は30。

概念図: bridgeポインタで隣のリストへO(1)ジャンプ

ヒント（段階的開示）

ヒント1: 方向性

「$L_1$で二分探索した結果の位置が分かれば、$L_2$での正しい位置も『そう遠くない場所』にあるはず」という直感が出発点。$L_1$と$L_2$の間にvalueベースの橋渡し情報を前もって埋め込んでおければ、$L_2$での二分探索を省略できる。

ヒント2: アプローチ

$k$番目のリストから逆順に「拡張カタログ」$A_k,A_{k-1},\dots,A_1$を構築する。$A_k=L_k$（各要素は自分自身を指すdownポインタを持つ）。$A_i$は、$L_i$の実要素と、$A_{i+1}$から1つおきに間引いたサンプル（末尾は必ず含める）をマージして作る。マージ後の各要素はdown（自分の値以上で最小の$L_i$の実要素の添字）とbridge（自分の値以上で最小のサンプルとして採用された$A_{i+1}$上の位置）の2ポインタを持つ。クエリ$x$は$A_1$で二分探索して開始位置を得た後、各レベルでbridgeを辿って移動する。ただし1つおきの間引きにより真の答えが1つ手前にずれている場合があるので、bridgeの位置と1つ手前の位置を元のクエリ値と比較し、必要なら1つ手前を採用する。

ヒント3: 誘導（コード骨格）

p = bisect_left(A[0]の値配列, x)      # 最初だけ二分探索 O(log N)
res0 = L[0][A[0][p]['down']]

bridge = A[0][p]['bridge']
for i in range(1, k):
    q = bridge
    if q > 0 and A[i][q-1]['val'] >= x:  # 間引きによるズレをここで補正
        q -= 1
    res_i = L[i][A[i][q]['down']]
    bridge = A[i][q]['bridge']

模範解答 (Python)

import sys, bisect

INF = float('inf')

def build(lists):
    k = len(lists)
    Cs = [lst + [INF] for lst in lists]
    A = [None] * k
    A[k - 1] = [{'val': v, 'down': i} for i, v in enumerate(Cs[k - 1])]
    for i in range(k - 2, -1, -1):
        nxt = A[i + 1]
        sample_pos = list(range(0, len(nxt), 2))
        if sample_pos[-1] != len(nxt) - 1:
            sample_pos.append(len(nxt) - 1)
        Ci = Cs[i]
        merged = []
        ri = si = 0
        while ri < len(Ci) or si < len(sample_pos):
            if ri < len(Ci) and (si >= len(sample_pos) or Ci[ri] <= nxt[sample_pos[si]]['val']):
                merged.append((Ci[ri], True, ri)); ri += 1
            else:
                merged.append((nxt[sample_pos[si]]['val'], False, sample_pos[si])); si += 1
        A_i = [None] * len(merged)
        cur_down = len(Ci) - 1
        cur_bridge = len(nxt) - 1
        for j in range(len(merged) - 1, -1, -1):
            val, is_real, payload = merged[j]
            if is_real:
                cur_down = payload
            else:
                cur_bridge = payload
            A_i[j] = {'val': val, 'down': cur_down, 'bridge': cur_bridge}
        A[i] = A_i
    return A, Cs

def query_all(A, Cs, x):
    res = [None] * len(A)
    lst0 = A[0]
    vals0 = [e['val'] for e in lst0]
    p = bisect.bisect_left(vals0, x)
    down = lst0[p]['down']
    res[0] = Cs[0][down] if Cs[0][down] != INF else -1
    bridge = lst0[p]['bridge']
    for i in range(1, len(A)):
        q = bridge
        if q > 0 and A[i][q - 1]['val'] >= x:
            q -= 1
        down = A[i][q]['down']
        res[i] = Cs[i][down] if Cs[i][down] != INF else -1
        if i + 1 < len(A):
            bridge = A[i][q]['bridge']
    return res

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    k = int(data[idx]); idx += 1
    lists = []
    for _ in range(k):
        n = int(data[idx]); idx += 1
        vals = [int(data[idx + j]) for j in range(n)]
        idx += n
        lists.append(vals)
    Q = int(data[idx]); idx += 1
    A, Cs = build(lists)
    out = []
    for _ in range(Q):
        x = int(data[idx]); idx += 1
        res = query_all(A, Cs, x)
        out.append(' '.join(map(str, res)))
    print('\n'.join(out))


solve()

計算量: 構築 $O(\sum n_i)$、クエリ1回あたり $O(\log N + k)$。ランダム300ケース（空リストを含む）でbrute-force bisectと一致することを確認済み。

Step-by-Step 解説

1番兵で境界処理を単純化
各リストの末尾に$+\infty$（番兵）を追加し、down/bridgeが常に有効なインデックスを指すようにする。出力時に番兵なら-1に変換するだけでよい。

2後ろから前へ、1つおきの間引きでカタログを構築
$A_i$は「$L_i$の実要素」と「$A_{i+1}$から1つおきに間引いたサンプル（末尾は必ず含める）」をマージ。これにより合計サイズが$O(\sum n_i)$に収まる。

3down/bridgeは右から左への走査で確定
マージ後の配列を右（大きい値）から左へ走査し、「直近に見た実要素」と「直近に見たサンプル」を更新し続ける。

4クエリ時は「1つ手前」の補正が必須
bridgeが指す位置は間引きで飛ばされた要素が真の答えである可能性があるため、元のクエリ値と比較し必要なら1つ減らす。この補正は各レベル高々1回の比較でO(k)に収まる。

よくあるミス

ミス	原因	正しい書き方
補正時にマージ後の値ではなく元のxと比較し忘れる	サンプルの値と比較すると関係が壊れて誤った位置に補正する	常に元のクエリ値xとA[i][q-1]['val']を比較する
間引きで末尾（番兵）を含め忘れる	偶数長の場合、最後の要素が漏れることがある	sample_pos[-1] != len(nxt)-1なら明示的に末尾を追加する
最終レベルでもbridgeを参照してしまう	末端のリストには次のレベルが存在しない	ループ内でi+1 < len(A)のときのみbridgeを更新する
空のリストが混在する場合の境界処理漏れ	全要素が番兵のみになるため間引き位置計算を誤りやすい	番兵を含む配列全体に同じロジックを一貫して適用すれば特別扱い不要

次のステップ

発展: 動的な要素追加（永続化構造や平衡二分探索木との組み合わせでオンライン更新に対応する）
発展: 2次元探索（幾何の平面走査アルゴリズムと組み合わせて使う古典的な応用例が多い）
次回予告: Ladder Decomposition（長path分解による真の$O(1)$ Level Ancestor Query）

自己評価

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

Day 107-Q3 — Fractional Cascading（複数ソート済み配列の一括探索）

問題