集訓(xùn)隊(duì)作業(yè)解題報(bào)告

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

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

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

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

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

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