問題
$N$ 頂点の素集合データ構造に対し $Q$ 個のクエリをオンラインで処理せよ。過去の任意のバージョンを参照できる完全永続版である。
| 種別 | 形式 | 意味 |
|---|---|---|
| 併合 | 1 v a b | バージョン $v$ から $a,b$ を併合し新バージョンを作る |
| 判定 | 2 v a b | バージョン $v$ で $a,b$ が同集合か（1/0） |
バージョン0は初期状態（全孤立）。$i$ 番目の更新クエリで作られるバージョンは $i$ 番。
制約
$1 \le N \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$
$0 \le v \le$ 既存バージョン番号
$1 \le a, b \le N$
入出力例
入力例 1
4 5
1 0 1 2
1 1 3 4
2 1 1 2
2 1 3 4
2 2 3 4出力例 1
1
0
1概念図: 永続配列（Copy-on-Write 完全二分木）
ヒント（段階的開示）
ヒント1: 方向性
経路圧縮は parent を破壊的に書き換えるため永続化と両立しない。union by rank のみで木の高さを $O(\log N)$ に保証し、配列を永続配列（完全二分木）で表現する。
ヒント2: アプローチ
parent[]とrank[]を永続配列で管理find: 圧縮せず根まで辿る（$O(\log N)$ 段 × アクセス $O(\log N)$）union: 2根の rank 比較、永続配列の1点更新で新バージョン生成
ヒント3: 実装骨格
# 永続配列: 完全二分木、1点更新は根→葉パスのみコピー
def update(node, pos, v, lo, hi): ... # 新ノードid返す
def get(node, pos, lo, hi): ...
# union by rank
ra, rb = find(pr, a), find(pr, b)
if rank[ra] < rank[rb]: ra, rb = rb, ra
npr = update(pr, rb, ra) # rb の親を ra に模範解答 (Python)
import sys
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
Q = int(data[idx]); idx += 1
size = 1
while size < N:
size <<= 1
lc = [0]; rc = [0]; val = [0] # node 0 = dummy
def build(arr):
def rec(lo, hi):
if hi - lo == 1:
val.append(arr[lo] if lo < len(arr) else 0)
lc.append(0); rc.append(0)
return len(val) - 1
mid = (lo + hi) >> 1
l = rec(lo, mid); r = rec(mid, hi)
val.append(0); lc.append(l); rc.append(r)
return len(val) - 1
return rec(0, size)
def get(node, pos, lo, hi):
while hi - lo > 1:
mid = (lo + hi) >> 1
if pos < mid:
node = lc[node]; hi = mid
else:
node = rc[node]; lo = mid
return val[node]
def update(node, pos, v, lo, hi):
if hi - lo == 1:
val.append(v); lc.append(0); rc.append(0)
return len(val) - 1
mid = (lo + hi) >> 1
if pos < mid:
nl = update(lc[node], pos, v, lo, mid)
val.append(0); lc.append(nl); rc.append(rc[node])
else:
nr = update(rc[node], pos, v, mid, hi)
val.append(0); lc.append(lc[node]); rc.append(nr)
return len(val) - 1
par_roots = [build(list(range(size)))]
rnk_roots = [build([0] * size)]
def find(pr, x):
while True:
p = get(pr, x, 0, size)
if p == x:
return x
x = p
out = []
for _ in range(Q):
t = int(data[idx]); v = int(data[idx+1])
a = int(data[idx+2]) - 1; b = int(data[idx+3]) - 1
idx += 4
pr = par_roots[v]; rr = rnk_roots[v]
if t == 1:
ra = find(pr, a); rb = find(pr, b)
if ra == rb:
par_roots.append(pr); rnk_roots.append(rr)
else:
rka = get(rr, ra, 0, size); rkb = get(rr, rb, 0, size)
if rka < rkb:
ra, rb = rb, ra; rka, rkb = rkb, rka
npr = update(pr, rb, ra, 0, size)
nrr = update(rr, ra, rka + 1, 0, size) if rka == rkb else rr
par_roots.append(npr); rnk_roots.append(nrr)
else:
out.append('1' if find(pr, a) == find(pr, b) else '0')
sys.stdout.write('\n'.join(out) + ('\n' if out else ''))
solve()
Step-by-Step 解説
1なぜ経路圧縮を使えないか
圧縮は find のたびに parent を破壊的更新し過去バージョンを壊す。永続化と両立しないため union by rank のみで高さ $O(\log N)$ を保証。
圧縮は find のたびに parent を破壊的更新し過去バージョンを壊す。永続化と両立しないため union by rank のみで高さ $O(\log N)$ を保証。
2永続配列
配列を完全二分木で表現。1点更新は根→葉のパス $O(\log N)$ ノードだけ新規コピー、他は旧ノード共有。
配列を完全二分木で表現。1点更新は根→葉のパス $O(\log N)$ ノードだけ新規コピー、他は旧ノード共有。
3find
圧縮なしで根まで辿る。rank併合で高さ $O(\log N)$、各 get が $O(\log N)$ なので find は $O(\log^2 N)$。
圧縮なしで根まで辿る。rank併合で高さ $O(\log N)$、各 get が $O(\log N)$ なので find は $O(\log^2 N)$。
4union
2根の rank を比較、小さい木を大きい木にぶら下げる。parent（+同rankなら rank）の1点更新で新バージョン。
2根の rank を比較、小さい木を大きい木にぶら下げる。parent（+同rankなら rank）の1点更新で新バージョン。
5クエリ処理
更新は新バージョンを push、判定は参照のみ。全体 $O(Q \log^2 N)$。
更新は新バージョンを push、判定は参照のみ。全体 $O(Q \log^2 N)$。
計算量
find: $O(\log^2 N)$（高さ $\log N$ × アクセス $\log N$）
union: $O(\log^2 N)$
全体: $O(Q \log^2 N)$
空間: $O((N + Q)\log N)$（差分ノードのみ）
union: $O(\log^2 N)$
全体: $O(Q \log^2 N)$
空間: $O((N + Q)\log N)$（差分ノードのみ）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 経路圧縮を使う | 過去バージョン破壊 | rank/size併合のみ |
| 同集合unionで新バージョン未発行 | バージョン番号ずれ | 変化なしでも根を複製push |
| 再帰深さ超過 | size=2^18 で再帰 | get は反復化 / setrecursionlimit |
| rank更新条件ミス | 等rank時のみ+1 | if rka == rkb: rank++ |
次のステップ
- 発展問題: 永続Union-Findを用いた並列二分探索・オフライン動的MST
- 類題: Persistent Segment Tree、関数型データ構造
- 応用: バージョン管理、undo可能なグラフ連結性