Luogu 🟣 P8819 [CSP-S 2022] 星战

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P8819 [CSP-S 2022] 星战

Problem Statement

題目簡述

在星際戰爭中，有 $n$ 個據點和 $m$ 條單向蟲洞。
指揮部定義一個絕佳的「反攻」時刻需同時滿足所有據點皆可：

1. 實現連續穿梭：每個據點出發的可用蟲洞「恰好只有一個」。
2. 實現反擊：從任何據點出發，都能不斷進行蟲洞穿梭（即能夠走入無限循環的環中）。

戰局中會發生 $q$ 次變化指令，分別為以下四種操作：

1. 摧毀特定的單向蟲洞 $u \to v$。
2. 摧毀據點 $v$（導致所有指向 $v$ 的蟲洞被一同摧毀，但不影響從 $v$ 出發的蟲洞）。
3. 修復特定的單向蟲洞 $u \to v$。
4. 修復據點 $v$（導致所有指向 $v$ 的蟲洞被一同修復）。

每執行一次指令，都需要判斷當前時刻的可用蟲洞是否能發起「反攻」。

Constraints

約束條件

• $1 \le n \le 5 \times 10^5$
• $1 \le m \le 5 \times 10^5$
• $1 \le q \le 5 \times 10^5$
• 保證圖中沒有自環或重邊。

---

思路：和雜湊 (Sum Hash)

1. 化簡判定條件

題目的「反攻」要求兩件事——「連續穿梭」（每個點出度恰為 1）與「實現反擊」（每個點都能走進環）。

從圖論的角度來看，當一張有向圖每個節點的出度皆恰為 1 時，這整張圖必定會構成基環內向森林。基環內向森林是由若干棵「基環內向樹」所組成，而基環內向樹的特性是：圖中包含唯一的一個有向環，且其餘分支的邊最終皆單向導通至該環上。

因此，只要滿足所有點出度皆為 1，從任意節點出發沿著唯一的出邊前進，最終必然能走入環中，這意味著第二個「反擊」條件將自動成立。

結論

兩個看似複雜的條件可完美等價為一個：每次操作後，是否所有節點的出度皆恰好為 1？

2. 正難則反：從維護出度轉向維護入度

直覺上，既然最終條件聚焦於「出度」，直接維護每個點的出度似乎最合理。但觀察操作 2 與 4，它們都是針對某個終點 $v$ 的批量操作（一次摧毀或修復所有指向 $v$ 的邊）。若要藉此逐一找到所有對應的起點來更新出度，最壞情況下单次操作需耗費 $\mathcal{O}(n)$ 時間，這在 $q=5 \times 10^5$ 的規模下必定導致 TLE。

此時我們可以運用「正難則反」的思想：既然操作的核心是修改「入邊」，何不轉而維護每個點的入度？如此一來，無論是修改單邊，還是批量修改所有入邊（直接將 $v$ 的入度歸零或重置），都能夠在 $\mathcal{O}(1)$ 內輕鬆完成。

然而，新問題隨之而來：我們雖然能以 $\mathcal{O}(1)$ 維護全圖的「總入度」（必定等於「總出度」），但單純比較「總入度是否等於 $n$」無法保證「每個點的出度皆恰好為 1」（例如：某點出度為 2，某點出度為 0，總和依舊是 $n$）。

3. 和雜湊 (Sum Hash)：從隨機權重著手

若要保證「每個點的出度皆恰好為 1」，我們可以首先為圖上的每個節點 $u$ 賦予一個大範圍的隨機權數 $W_u \in [1, 2^{64}-1]$。

當題目的理想條件成立時，也就是對於所有節點 $u$，其出度 $\text{outdeg}(u)$ 都正好是 1。這表示若我們計算全圖「出度 $\times$ 權重」的總和，結果勢必會等於：

$$\text{tgt} = \sum_{u=1}^n \bigl(1 \times W_u\bigr) = \sum_{u=1}^n W_u$$

此即為我們期望達到的目標雜湊值。

轉向入邊視角的等價計算

問題來了，我們該如何快速算出「當前圖上的出度權重和」 $h = \sum_{u=1}^n \bigl(\text{outdeg}(u) \times W_u\bigr)$？

觀察這張圖：每一條從 $u$ 出發的邊，同時也是指向某個終點 $v$ 的入邊。因此，「所有起點的出度權重總和」在數學上完全等價於「所有終點的入邊權重總和」。

我們定義 $\text{curr}_v$ 為「當前所有指向 $v$ 的起點之權重和」：

$$\text{curr}_v = \sum_{(u,v) \in E_{\text{active}}} W_u$$

那麼全域的雜湊值便可輕易地從終點視角累加得出：$h = \sum_{v=1}^n \text{curr}_v$。
只要每次驗證 $h = \text{tgt}$，由於 $W_u$ 來自極大的隨機空間，我們幾乎能 $100\%$ 確定所有 $\text{outdeg}(u) = 1$。

由於我們維護的對象是「終點的入邊權重和」，四種操作（同步更新 $\text{curr}_v$ 與 $h$）都只涉及常數次加減，均為 $\mathcal{O}(1)$：

1. 移除 $(u, v)$：$\text{curr}_v \gets \text{curr}_v - W_u$
2. 移除 $v$ 全部入邊：$\text{curr}_v \gets 0$
3. 恢復 $(u, v)$：$\text{curr}_v \gets \text{curr}_v + W_u$
4. 恢復 $v$ 全部入邊：$\text{curr}_v \gets \text{base}_v$（$\text{base}_v$ 為初始時指向 $v$ 的權重總和）

每次操作後只需檢查 $h = \text{tgt}$ 即可回答詢問。

複雜度分析

• 時間複雜度：$\mathcal{O}(n + m + q)$
  • 對應 $q$ 次詢問，每次詢問及維護狀態僅需 $\mathcal{O}(1)$，處理所有詢問的總耗時為 $\mathcal{O}(q)$。
• 空間複雜度：$\mathcal{O}(n)$
  • 無需建立鄰接串列或保存具體的圖結構，僅需維護三個長度為 $n$ 的陣列：節點權重 W、初始入邊權重 base、當前入邊權重 curr。

---

Code

from random import randint

U = (1 << 64) - 1


def solve():
    n, m = map(int, input().split())

    W = [randint(1, U) for _ in range(n)]  # 節點隨機權重
    tgt = sum(W)  # 目標雜湊值

    base = [0] * n  # base[v]: 初始入邊權重和
    for _ in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        base[v] += W[u]
    curr = base[:]  # curr[v]: 當前入邊權重和

    h = sum(curr)  # 全域雜湊值

    q = int(input())
    ans = []
    for _ in range(q):
        op, *args = map(int, input().split())
        if op == 1:  # 移除 (u, v) 邊
            u, v = map(lambda x: x - 1, args)
            h -= curr[v]
            curr[v] -= W[u]
            h += curr[v]
        elif op == 2:  # 移除 v 的全部入邊
            v = args[0] - 1
            h -= curr[v]
            curr[v] = 0
        elif op == 3:  # 恢復 (u, v) 邊
            u, v = map(lambda x: x - 1, args)
            h -= curr[v]
            curr[v] += W[u]
            h += curr[v]
        else:  # 恢復 v 的全部入邊
            v = args[0] - 1
            h -= curr[v]
            curr[v] = base[v]
            h += curr[v]
        ans.append("YES" if h == tgt else "NO")
    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()