BZOJ 1095. [ZJOI2007]Hide 捉迷藏

Brief description:

給定一棵樹,每個節點要麼是黑色,要麼是白色,能執行兩個操作:
。。。把某一個點取反色,返回距離最遠的黑色點對。

Analysis:

。。。... 。。鏈分治和邊分治的方法參見 Qtree 4 那篇。。)
。。這裡記錄一下括弧序列的方法。。。)

定義一種對一棵樹的括弧編碼。這種編碼方式很直觀,所以,這裡不給出嚴格的定義,用以下這棵樹為例:

(圖片自行腦補。。。)

可以先序遍歷後寫成:[A[B[E][F[H][I]]][C][D[G]]]
去掉字母后的串:[[[][[][]]][][[]]]

就稱為這棵樹的括弧編碼。(這個編碼本質上是由深度優先遍歷得到的)
考察兩個結點,如 E 和 G ,

取出介於它們之間的那段括弧編碼 :][[][]]][][[
把匹配的括弧去掉,得到:]][[

我們看到 2 個 ] 和 2 個 [,也就是說,在樹中,從 E 向上爬 2 步,再向下走 2 步就到了 G。
注意到,題目中需要的信息只有這棵樹中點與點的距離,所以,貯存編碼中匹配的括弧是沒有意義的。
因此,對於介於兩個節點間的一段括弧編碼 S,可以用一個二元組 (a, b) 描述它,即這段編碼去掉匹配括弧後有 a 個 ] 和 b 個 [。
所以,對於兩個點 PQ,如果介於某兩點 PQ 之間編碼 S 可表示為 (a, b),PQ 之間的距離就是 a+b。

也就是說,題目只需要動態維護:max{a+b | S』(a, b) 是 S 的一個子串,且 S』 介於兩個黑點之間},
這裡 S 是整棵樹的括弧編碼。我們把這個量記為 dis(s)。

現在,如果可以通過左邊一半的統計信息和右邊一半的統計信息,得到整段編碼的統計,這道題就可以用熟悉的線段樹解決了。

這需要下面的分析。

考慮對於兩段括弧編碼 S1(a1, b1) 和 S2(a2, b2),如果它們連接起來形成 S(a, b)。
注意到 S1、S2 相連時又形成了 min{b, c} 對成對的括弧,合併後它們會被抵消掉。(?..這裡 b, c 應該分別是指 b1 和 a2。。。

所以:

當 a2 < b1 時第一段 [ 就被消完了,兩段 ] 連在一起,例如:
] ] [ [  +  ] ] ] [ [  =  ] ] ] [ [
當 a2 >= b1 時第二段 ] 就被消完了,兩段 [ 連在一起,例如:
] ] [ [ [  +  ] ] [ [  =  ] ] [ [ [ (?..反了?。。。

這樣,就得到了一個十分有用的結論:

當 a2 < b1 時,(a,b) = (a1-b1+a2, b2),
當 a2 >= b1 時,(a,b) = (a1, b1-a2+b2)。

由此,又得到幾個簡單的推論:

(i) a+b = a1+b2+|a2-b1| = max{(a1-b1)+(a2+b2), (a1+b1)+(b2-a2)}
(ii) a-b = a1-b1+a2-b2
(iii) b-a = b2-a2+b1-a1

由 (i) 式,可以發現,要維護 dis(s),就必須對子串維護以下四個量:

right_plus:max{a+b | S』(a,b) 是 S 的一個後綴,且 S』 緊接在一個黑點之後}
right_minus:max{a-b | S』(a,b) 是 S 的一個後綴,且 S』 緊接在一個黑點之後}
left_plus:max{a+b | S』(a,b) 是 S 的一個前綴,且有一個黑點緊接在 S 之後}
left_minus:max{b-a | S』(a,b) 是 S 的一個前綴,且有一個黑點緊接在 S 之後}

這樣,對於 S = S1 + S2,其中 S1(a, b)、S2(c, d)、S(e, f),就有

(e, f) = b < c ? (a-b+c, d) : (a, b-c+d)
dis(S) = max{dis(S1), left_minus(S2)+right_plus(S1), left_plus(S2)+right_minus(S1), dis(S2)}

那麼,增加這四個參數是否就夠了呢?
是的,因為:

right_plus(S) = max{right_plus(S1)-c+d, right_minus(S1)+c+d, right_plus(S2)}
right_minus(S) = max{right_minus(S1)+c-d, right_minus(S2)}           
left_plus(S) = max{left_plus(S2)-b+a, left_minus(S2)+b+a, left_plus(S1)}   
left_minus(S) = max{left_minus(S2)+b-a, left_minus(S1)}               

這樣一來,就可以用線段樹處理編碼串了。實際實現的時候,在編碼串中加進結點標號會更方便,對於底層結點,如果對應字元是一個括弧或者一個白點,那 么right_plus、right_minus、left_plus、left_minus、dis 的值就都是 -maxlongint;如果對應字元是一個黑點,那麼 right_plus、right_minus、left_plus、left_minus 都是 0,dis 是 -maxlongint。

現在這個題得到圓滿解決,回顧這個過程,可以發現用一個串表達整棵樹的信息是關鍵,這一「壓」使得線段樹這一強大工具得以利用.. .

———— 以上摘自 NOI08 冬令營論文 《數據結構的提煉與壓縮》 by cqx 。。。

線段樹維護括弧序列(2s+- ...
鏈分治(2.5s+ ...
邊分治。(23.0s++

External link:

http://www.lydsy.com/JudgeOnline/problem.php?id=1095
http://hi.baidu.com/wjbzbmr/blog/item/2b02ec1cda7abbfa1ad57656.html