Day 102-Q1 | 区間Union-Find（Next-Pointer DSU）

問題

$1$ から $D$ までの番号がついた「日」がある。最初、すべての日は空いている。$N$ 件の予約リクエストが順番に来る。$i$ 件目のリクエストは「日 $d_i$ 以降で最も早い空いている日」を希望する。条件を満たす空き日があればその場で予約済みにして日番号を出力し、なければ -1 を出力する。

「$x$以降で最初に空いている場所を見つけて埋める」操作を、経路圧縮つきUnion-Findの Next-Pointer DSU（区間Union-Find） を使ってならし $O(\alpha(D))$ で処理する。`parent[x]` を「$x$以降で最初に空いている（か未調査の）日」を指すポインタとして扱い、日$x$を埋めたら `parent[x]` を `find(x+1)` にマージする。

入力形式

D N
d_1
d_2
:
d_N

制約

$1 \le D \le 2\times10^5$

$1 \le N \le 2\times10^5$

$1 \le d_i \le D$

すべて整数

入出力例

入力例1

出力例1

1件目:3→予約。2件目:3は埋まっているので4→予約。3件目:1→予約。4件目:5→予約。5,6件目:5以降(5)はすべて埋まっている→-1（2は空いているが5以降ではないので対象外）。

入力例2

出力例2

1
2
3

3件とも「1以降で最初の空き」を求めるので、1→2→3の順に埋まっていく。

概念図

ヒント（段階的開示）

ヒント1: 方向性

「$d_i$から$D$まで1つずつ空きを線形探索する」のが最も素朴な方法だが、同じ日を何度も「埋まっているかどうか」チェックし直すのが無駄。一度「この日は埋まっている」と分かったら、次回以降その事実を高速に引き継げる仕組みが欲しい。

ヒント2: アプローチ

Union-Findの「経路圧縮」の仕組みをそのまま使う。`parent[x] = x`で初期化し、`find(x)`が「$x$以降で最初の空き日」を返すように設計する。日$x$を予約したら`union(x, x+1)`（`parent[find(x)] = find(x+1)`）することで、次に`find(x)`を呼んだときは自動的に$x+1$以降を指すようになる。番兵として`parent[D+1] = D+1`を用意し、`find`の結果が$D+1$を超えたら「空きなし」と判定する。

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

parent = list(range(D + 2))  # D+1が番兵

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

for d in days:
    p = find(d)
    if p > D:
        print(-1)
    else:
        print(p)
        parent[p] = p + 1

経路圧縮つきUnion-Findとほぼ同じ実装で、ならし計算量が$O(\alpha(D))$になる。

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    D = int(data[idx]); idx += 1
    N = int(data[idx]); idx += 1

    parent = list(range(D + 2))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    out = []
    for _ in range(N):
        d = int(data[idx]); idx += 1
        p = find(d)
        if p > D:
            out.append("-1")
        else:
            out.append(str(p))
            parent[p] = p + 1

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


solve()

計算量: $O((D+N)\alpha(D))$（経路圧縮つきUnion-Findのならし解析による、実質ほぼ線形）。

Step-by-Step 解説

1DSUの初期化
`parent[x]=x`で$1$から$D+1$まで初期化。$D+1$は「これ以上空きがない」ことを表す番兵ノード。

2`find`の意味づけ
`find(x)`は「$x$以降で最初に空いている（もしくは番兵の）日」を返す。経路圧縮で繰り返し呼んでも均されて高速。

3予約とポインタの前進
`find(d)`で得た`p`が`D`以下なら予約し出力。同時に`parent[p]=p+1`として次回`p+1`以降を見るようポインタを更新。

4番兵による空きなし判定
`p>D`なら番兵`D+1`に到達＝それ以降空きなし。`-1`を出力するだけでDSUの状態変更は不要。

よくあるミス

ミス	原因	正しい書き方
番兵を用意せず`x>D`で例外処理を書く	配列外参照やIndexErrorを誘発する	`parent`のサイズを`D+2`にし`D+1`を番兵として組み込む
予約後に`union(p,p+1)`をせず放置	次回同じ`p`が再度返され重複予約されるバグになる	予約したら必ず`parent[p]=p+1`で前進させる
再帰による完全な経路圧縮を書く	$D$が大きいと再帰が深くなりRecursionErrorになる	反復（while）+パス半分圧縮を使い再帰を避ける
`find`が毎回$O(D)$だと誤解し別解法を用意する	経路圧縮による償却計算量の理解不足	$N$回の操作全体で$O((D+N)\alpha(D))$になることを理解する

次のステップ

発展: 「予約のキャンセル」も許可する場合（DSUでは削除ができないため、平衡二分探索木やBITでの二分探索など別のデータ構造が必要）
発展: 2次元版（グリッド上で「$(x,y)$以降で最初の空きマス」を探す、行ごとにDSUを持つ拡張）
次回予告: Generalized Suffix Automaton via Trie（複数文字列のTrie構築+SAM継承リンクによる一般化サフィックスオートマトン）

自己評価

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

Day 102-Q1 — 区間Union-Find（Next-Pointer DSU）

問題