集訓(xùn)隊作業(yè)解題報告

1、IOI2009國家集訓(xùn)隊作業(yè)：otoci解題報告 廣東中山一中 方展鵬Otoci解題報告廣東中山一中 方展鵬題目描述給出n個結(jié)點以及每個點初始時對應(yīng)的權(quán)值wi。起始時點與點之間沒有連邊。有3類操作：1、bridge A B：詢問結(jié)點A與結(jié)點B是否連通。如果是則輸出“no”。否則輸出“yes”，并且在結(jié)點A和結(jié)點B之間連一條無向邊。2、penguins A X：將結(jié)點A對應(yīng)的權(quán)值wA修改為X。3、excursion A B：如果結(jié)點A和結(jié)點B不連通，則輸出“impossible”。否則輸出結(jié)點A到結(jié)點B的路徑上的點對應(yīng)的權(quán)值的和。給出q個操作，要求在線處理所有操作。數(shù)據(jù)范圍：1 n 30000,

2、 1 q 300000, 0 wi 1000。時間限制：5s算法分析不難看出，由給出的n個點構(gòu)成的圖在任意時刻都是一個森林。并且由于已經(jīng)添加的邊不會被刪除，所以對于任意兩個結(jié)點x和y，如果在處理完第i個操作后，結(jié)點x到結(jié)點y的路徑為P，那么在處理完第i(ii)個操作后，若結(jié)點x與結(jié)點y連通，那么結(jié)點x到結(jié)點y的路徑依然為P。因此，如果題目不要求在線處理所有操作，我們可以用如下算法解決本題：1、先讀入所有操作，然后利用并查集將處理完所有bridge操作的森林S構(gòu)造出來。這步的時間復(fù)雜度為O(q+n)。2、對于森林S中所有的樹T，確定一個根，并且求出T的DFS序列。然后對于每個DFS序列都建一棵線

3、段樹，維護(hù)DFS序列中某一段序列的結(jié)點對應(yīng)的w值的和。這步的時間復(fù)雜度為O(n)。3、對于每個結(jié)點x，求出x向上“跳”2k條邊后到達(dá)的結(jié)點的編號。這步是為求LCA做好預(yù)處理，時間復(fù)雜度為O(nlogn)。4、從前往后處理每一個操作。對于bridge操作，我們可以通過并查集維護(hù)連通性來處理，這樣處理單次bridge操作的時間復(fù)雜度為O(1)。對于excursion操作，我們可以先通過并查集確定連通性，如果不連通則直接輸出“impossible”。否則，通過用線段樹維護(hù)的DFS序列，我們可以較快地求出結(jié)點x到它的祖先的路徑上的點對應(yīng)的權(quán)值的和。因此，對于操作excursion X Y，我們可以先求

4、出結(jié)點X和結(jié)點Y的最近公共祖先Z。那么問題就轉(zhuǎn)化為求X到Z以及Y到Z的路徑上的點對應(yīng)的權(quán)值和，這個問題可以通過線段樹輕松解決，這樣處理單次excursion操作的時間復(fù)雜度為O(logn)。而對于penguins操作，我們只需要在線段樹上修改就可以了，因此處理單次penguins操作的時間復(fù)雜度為O(logn)。綜上，這步的時間復(fù)雜度為O(qlogn)。整個算法的時間復(fù)雜度為O(nlogn+qlogn)。雖然題目要求在線處理所有的操作，但是我們依然嘗試用上面所說的離線算法的框架來解決這道題目。如果我們依然使用上述算法的框架，下面我們來看看需要維護(hù)哪些信息。首先，我們需要知道結(jié)點之間的連通情況；

5、其次，為了較快的求出LCA，我們需要知道每個結(jié)點x向上“跳”2k條邊后到達(dá)的結(jié)點的編號；最后，我們還需要知道當(dāng)前所有樹的DFS序列以及需要一種較為高效的數(shù)據(jù)結(jié)構(gòu)來維護(hù)某一段序列中的結(jié)點對應(yīng)的權(quán)值的和。有了這些信息，我們可以很容易地處理掉excursion操作，因此下面我們主要討論如何比較高效地維護(hù)這些信息。對于penguins操作，只需要維護(hù)DFS序列的數(shù)據(jù)結(jié)構(gòu)支持比較高效的修改操作就可以了，而這一點很多數(shù)據(jù)結(jié)構(gòu)都可以做到，因此下面我們著重討論如何處理bridge操作。我們先來看一個例子，看一下bridge操作后DFS序列發(fā)生了什么變化。不難看出bridge操作實際上就是重新構(gòu)造一段DFS序列

6、，然后將該序列插入到另一段DFS序列中的某個位置。另外，我們不難發(fā)現(xiàn)bridge操作每次都是將兩個不相交的結(jié)點集合合并。因此，在處理bridge操作時，我們可以采用啟發(fā)式合并 合并兩個不相交集合時，將大小較小的集合中的元素逐個添加到大小較大的集合中，以此來實現(xiàn)集合的合并。的方法來合并兩個點集，可以證明每個點最多只會被處理logn次，這樣維護(hù)LCA信息的總時間復(fù)雜度為O(nlog2n)。而為了維護(hù)DFS序列的信息，我們需要一個能夠較快地處理插入一段序列，求某一段子序列的和，以及修改序列中某一個元素的值的數(shù)據(jù)結(jié)構(gòu)。Treap、Square List和Splay Tree都能比較好地勝任上面的操作，其中用Treap維護(hù)的時間復(fù)雜度為O(nlog2n+qlogn)，用Square List維護(hù)的時間復(fù)雜度為，用Splay Tree維護(hù)的時間復(fù)雜度為O(nlogn+qlogn)。考慮到時間復(fù)雜度與編程復(fù)雜度