Day 110-Q3 — オフライン動的連結性（時間軸セグ木 + ロールバックDSU）

2026-08-02 赤色 Master / Phase 8+ ★★★★★★★★★ 辺の有効期間を時間軸セグ木に載せロールバック可能なDSUで処理

問題

$N$頂点のグラフに $M$本の辺があり、$i$番目の辺$(u_i,v_i)$は時刻$l_i$から$r_i$まで（両端含む）存在する。$Q$個のクエリ「時刻$t_j$において$x_j,y_j$は連結か」にオフラインで答えよ。

入力形式

N M Q T
u_1 v_1 l_1 r_1
...
t_1 x_1 y_1
...

制約

$1 \le N,M,Q,T \le 10^5$
$1 \le l_i \le r_i \le T$
$1 \le t_j \le T$

入出力例

入力例1

4 3 3 3
1 2 1 3
3 4 2 3
2 3 3 3
1 1 4
2 1 4
3 1 4

出力例1

No
No
Yes

時刻1: 辺(1,2)のみ→非連結。時刻2: 辺(1,2),(3,4)→非連結。時刻3: 辺(1,2),(3,4),(2,3)全て有効→全連結。

概念図: 辺の有効区間を時間軸セグメント木に載せる

時刻1..3を葉に持つセグ木 + 各辺の有効区間を分解登録 [1,4] root [1,2] [3,4] t=1 t=2 t=3 辺(1,2,l=1,r=3) → ノード[1,2]と葉t=3に登録（O(log T)分解） DFSで根から葉へ辿りながらunion、葉でクエリに回答、戻り際にrollback

ヒント（段階的開示）

ヒント1: 方向性
Union-Findは分離に対応できない。各時刻ごとにグラフを再構築すると$O(T(N+M)\alpha(N))$と大きすぎる。辺の有効期間という区間情報を時間軸上でまとめて扱う発想が必要。
ヒント2: アプローチ
時刻$1..T$を葉とするセグ木を構築し、各辺の区間$[l,r]$を$O(\log T)$ノードに分解登録する。セグ木を根からDFSしながらロールバック可能なUnion-Find（union by size、経路圧縮なし）で辺を反映し、葉（1つの時刻）でその時刻のクエリに回答、親に戻るときはunionを取り消す。全体$O((N+M+Q)\log T \log N)$。
ヒント3: 誘導（コード骨格） 
history = []
def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        history.append(None); return
    if size[rx] < size[ry]:
        rx, ry = ry, rx
    parent[ry] = rx
    history.append((ry, rx, size[rx]))
    size[rx] += size[ry]

def rollback():
    rec = history.pop()
    if rec is None: return
    ry, rx, old_size = rec
    parent[ry] = ry
    size[rx] = old_size

模範解答 (Python)

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    def nxt():
        nonlocal idx
        v = input_data[idx]; idx += 1
        return int(v)

    n = nxt(); m = nxt(); q = nxt(); T = nxt()

    edges = []
    for _ in range(m):
        u = nxt(); v = nxt(); l = nxt(); r = nxt()
        edges.append((u, v, l, r))

    queries = []
    for j in range(q):
        t = nxt(); x = nxt(); y = nxt()
        queries.append((t, x, y))

    query_at = [[] for _ in range(T + 1)]
    for j, (t, x, y) in enumerate(queries):
        query_at[t].append(j)

    size_tree = 1
    while size_tree < T:
        size_tree *= 2
    seg = [[] for _ in range(2 * size_tree)]

    def update(node, node_l, node_r, l, r, edge_id):
        if r < node_l or node_r < l:
            return
        if l <= node_l and node_r <= r:
            seg[node].append(edge_id)
            return
        mid = (node_l + node_r) // 2
        update(2 * node, node_l, mid, l, r, edge_id)
        update(2 * node + 1, mid + 1, node_r, l, r, edge_id)

    for i, (u, v, l, r) in enumerate(edges):
        update(1, 1, size_tree, l, r, i)

    parent = list(range(n + 1))
    rank_ = [1] * (n + 1)
    history = []

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

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            history.append(None)
            return
        if rank_[rx] < rank_[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        old = rank_[rx]
        rank_[rx] += rank_[ry]
        history.append((ry, rx, old))

    def rollback():
        rec = history.pop()
        if rec is None:
            return
        ry, rx, old_rank_rx = rec
        parent[ry] = ry
        rank_[rx] = old_rank_rx

    ans = [None] * q

    def dfs(node, node_l, node_r):
        cnt = 0
        for edge_id in seg[node]:
            u, v, _, _ = edges[edge_id]
            union(u, v)
            cnt += 1
        if node_l == node_r:
            if node_l <= T:
                for j in query_at[node_l]:
                    t, x, y = queries[j]
                    ans[j] = "Yes" if find(x) == find(y) else "No"
        else:
            mid = (node_l + node_r) // 2
            dfs(2 * node, node_l, mid)
            dfs(2 * node + 1, mid + 1, node_r)
        for _ in range(cnt):
            rollback()

    sys.setrecursionlimit(500000)
    dfs(1, 1, size_tree)

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

solve()
計算量: $O((M\log T)\log N + Q)$。入力例1で No/No/Yes と一致することを確認済み。

Step-by-Step 解説

1辺の有効期間を時間軸セグ木に載せる
区間更新と同じ要領で$O(\log T)$ノードに登録する。
2DFSで有効な辺を積み上げる
ノードに登録された辺をUnion-Findに反映しながら根から葉へ辿る。
3葉でクエリに即答する
葉到達時のDSU状態はその時刻の全有効辺を反映済み。
4親に戻る際にロールバックする
経路圧縮なしのDSUなら変更点の記録だけで正確に巻き戻せる。
5マージテク・時間軸セグ木・ロールバックDSUの組み合わせ
オフラインクエリ処理の典型パターンとして押さえる。

よくあるミス

ミス原因正しい書き方
Union-Findで経路圧縮を使う経路圧縮は破壊的でロールバック不可能union by size/rankのみ使い経路圧縮しない
ロールバック時にサイズの巻き戻しを誤る変更前の親サイズの記録漏れunion時に変更前の親サイズだけ記録すれば復元できる
クエリを毎回全走査するDFSの各葉で$O(Q)$走査すると$O(TQ)$に悪化事前に時刻ごとのバケットを作る
セグ木サイズを$T$ぴったりにする完全二分木前提の再帰実装が崩れる$T$以上の最小の2冪を確保する

次のステップ

  • 発展: 連結成分数・成分サイズを扱う集約値付きロールバックDSUに拡張する
  • 発展: 二部グラフ判定（奇閉路検出）を拡張情報（頂点の色）付きDSUで解く
  • 発展: 完全オンラインな動的連結性にはEuler Tour Tree（Day110-Q2）が必要になることを理解する

自己評価

自分の回答

気づき・メモ