閱讀《記錄一類分治方法》筆記

題一

\(n\) 個點的無向圖，邊有邊權。\(q\) 次操作，每次操作是添加/刪除一條邊、修改一條邊的邊權、查詢最小生成樹這四種之一。

前言

其實只看了題一，后面都還沒看呢。

看到這個感覺和 P7457 [CERC2018] The Bridge on the River Kawaii 很像，感覺很牛。想看看這個做法能不能推廣到這題。

然后腦子有些混亂，覺得很能推廣啊，想寫一發代碼。然后代碼寫完發現 P7457 是詢問兩點連通性。這和最小生成樹不一樣。很搞笑了。

所以只能再開一篇把寫的東西搬過來了。

思路

原文對我來講有些簡略，這里會講的更詳細一點。

考慮我們有 \(O(m+q)\) 條邊，每條邊在一個時間區間內有權值 \(w_i\)，在其他時刻權值為 \(inf\)，求最小生成樹。離線。

設邊的全集是 \(E\)，存在一些時刻權值是 \(inf\) 的邊集是 \(Q\)。

把 \(Q\) 里所有邊的權值設為 \(-inf\)，跑一遍最小生成樹，選上的 \(E\) 里面的邊無論任何情況都是必選的。所有可以縮掉這些必選邊。這樣我們的點數變成了 \(O(|Q|)\)。

把 \(Q\) 里所有邊的權值設為 \(inf\)，跑一遍最小生成樹，沒有選上的 \(E\) 里面的邊無論任何情況都不會被選擇。所以可以刪掉這些沒用的邊。這樣我們的邊數又變成 \(O(|Q|)\) 了。

對于當前分治區間，集合 \(E\) 定義為所有時間區間包含了整個分治區間的邊。\(Q\) 定義為所有時間區間沒有包含整個分治區間的邊。

按照上面的方法，我們可以把點數和邊數都變成 \(O(|Q|)\)。

\(Q\) 有多少條邊？因為每次操作只會影響一條邊，并確定這條邊的時間區間的左/右端點。所以存在一個端點在當前分治區間內的邊的數量，關于分治區間長度線性，即 \(O(len)\)。

既然我們保證了分治區間的點數和邊數，那么每個分治區間把已經可以確定的點和邊確定，有效的點和邊留下即可。

總時間復雜度 \(O(q \log q)\)（并查集復雜度當常數看了）。