回文樹在線剖分？？？
Preface
蒟蒻剛學PAM，就做到一道惡心PAM+LCT題，然而蒟蒻并不會LCT，于是想出一種奇妙的解法，在此分享，歡迎討論交流，
The problem
Source
IOI2017中國國家隊候選隊論文集 --- 回文樹及其應用 翁文濤 --- 5.5 AlphaDog（原創）
Also in 本校OJ Problem4427
Description
對于一個串的特殊值F(s)定義為
\[\large F_s= \sum_{1 \leq x \leq y \leq|s|} LCP(x,y) \]其中LCP即Longest Common Palindrome的縮寫，也就是說LCP(x,y)表示最長的字串t的長度，其中t要滿足三個條件：
- t是回文的
- 存在一個i，滿足s[i...x]=t
- 存在一個j，滿足s[j...y]=t
一開始有一個空串s，接下來進行q次插入，每次在串的末尾加入一個新的字符，每次加入后，詢問當前串的F值，強制在線，
Data Constraint
\[q \leq 10^5 \\\ \large \Sigma 為小寫字符集 \]Analysis
容易看出：LCP(x,y) 其實就是 x,y在回文樹上的兩點 在fail樹上的lca處的 len值
每加入一個字符后，F(s)會增加一些值——
這部分我們可以把貢獻都放在lca處統計
不強制在線的資料有20% -_- 只需要先把整顆樹跑出來再樹剖
100%
強制在線則容易想到 Link/Cut Tree
不會啊！！！怎么辦？？？
回到樹剖——我們的瓶頸在于無法即時得到合適的剖分方式(重兒子)
blingbling 腦中跳出一個回文樹的有趣性質
Lemma
設x為fail樹上一個節點，diff[x]為 x與 Fa[x] 兩點的 Len 的差值
則 x 到樹根的fail鏈，可以劃分為O(log(Len_x))條 diff 值相等的鏈
引理證明可參考oi-wiki最小回文劃分部分
這樣我們就可以這樣定義x的重兒子son了：son為 x的兒子中 滿足 與 x 的 diff 相等的那個
如果沒有滿足的 那x就沒有son，那如果有多個呢？？？
這個問題在我碼完3k代碼后蹦出，嚇了我一跳，事實上，這種情況極少，且不影響做法，
理由：
設 不同的兩點 x，y 有公共父親 z，z 的父親為 fz，設 x，y 所代表的串分別為X，Y，
若 x，y 均滿足成為z的重兒子的條件，則顯然 |X|=|Y|，又因為X不同于Y，則 diff[x] > |X|/2 ，那么 Len_fz<0，則fz只可能為1節點，這時z只要隨便選一個滿足條件的兒子作son就行啦！
復雜度——O(q log^2 q)
Postscript
由于本題的LCT做法不需要cut一類操作，本校其他dalao只碼了2.1k，而我用我的方法碼了3.0k，，，
不過從方法的簡單易懂來說，還是不錯的，還特別創新不是嗎，嘻嘻，
大佬們還YY出 平衡規劃等 神奇做法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145110.html
標籤：其他