Day 056-Q2 — Offline Dynamic Reachability（DAG・辺削除分割統治）

問題

$N$ 頂点の DAG と $M$ 本の辺が与えられる。各辺 $e_k = (u_k, v_k)$ には有効期間 $[a_k, b_k)$ がある。$Q$ 個のクエリ $(t_i, s_i, g_i)$: タイムステップ $t_i$ において $s_i \to g_i$ へ到達可能か答えよ。

入出力例

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

No
Yes
Yes
No

$t=0$: 辺1→2のみ有効 → 1→3不可。$t=1$: 辺1→2と2→3有効 → 1→3可。 $t=2$: 辺2→3と3→4有効 → 1→4不可（1→2が切れている）。$t=3$: 全辺切れ → 不可。

概念図: タイムセグメント木と分割統治

ヒント（段階的開示）

def dfs(node, adj):
    local = adj[:]           # 親からコピー
    for u, v in seg[node]:
        local[u] |= (1 << v) # bitset に辺追加

    if node >= SIZE:         # 葉
        t = node - SIZE
        if t < Q:
            reach = warshall(local)
            for qi, s, g in leaf_queries[t]:
                ans[qi] = 'Yes' if (reach[s] >> g) & 1 else 'No'
        return

    dfs(node*2,   local)
    dfs(node*2+1, local)

模範解答 (Python)

コピーimport sys
from sys import setrecursionlimit
input = sys.stdin.readline
setrecursionlimit(300000)

def solve():
    N, M, Q = map(int, input().split())
    edges_raw = []
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        edges_raw.append((u-1, v-1, a, b))
    queries_raw = []
    for i in range(Q):
        t, s, g = map(int, input().split())
        queries_raw.append((t, s-1, g-1))

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

    def add_edge(l, r, e):
        l += SIZE; r += SIZE
        while l < r:
            if l & 1: seg[l].append(e); l += 1
            if r & 1: r -= 1; seg[r].append(e)
            l >>= 1; r >>= 1

    for u, v, a, b in edges_raw:
        if a < b:
            add_edge(a, b, (u, v))

    leaf_queries = [[] for _ in range(SIZE)]
    for i, (t, s, g) in enumerate(queries_raw):
        leaf_queries[t].append((i, s, g))

    ans = ['No'] * Q

    def warshall(adj):
        reach = adj[:]
        for k in range(N):
            mk = reach[k]
            for i in range(N):
                if (reach[i] >> k) & 1:
                    reach[i] |= mk
        return reach

    def dfs(node, adj):
        local = adj[:]
        for u, v in seg[node]:
            local[u] |= (1 << v)
        if node >= SIZE:
            t = node - SIZE
            if t < Q and leaf_queries[t]:
                reach = warshall(local)
                for qi, s, g in leaf_queries[t]:
                    if (reach[s] >> g) & 1:
                        ans[qi] = 'Yes'
            return
        dfs(node * 2, local)
        dfs(node * 2 + 1, local)

    dfs(1, [0] * N)
    print('\n'.join(ans))

solve()

Step-by-Step 解説

Step 1: タイムセグメント木への辺配置

辺の有効区間 $[a, b)$ をセグメント木上の標準区間分解で $O(\log Q)$ ノードに配置する。

Step 2: DFS による辺の累積

セグメント木をDFSで下る際、現在のノードに配置された辺を隣接行列（Pythonの大整数ビット演算）にORで追加する。子に渡すときはコピーを取るので $O(N)$ のコピーが発生。

Step 3: Warshall-Floyd で推移閉包

$N \le 500$ の bitset 表現（1頂点 = 1整数）で $O(N^2)$ の推移閉包計算。Python の大整数ビット演算はワード並列で定数倍有利。

Step 4: クエリ処理

葉ノードで対応するクエリの $(s, g)$ について (reach[s] >> g) & 1 を確認。

計算量

よくあるミス

次のステップ

• 無向動的グラフの連結性（Offline Dynamic Connectivity + Undo DSU）
• DAG 上の最長路の動的変化

自己評価