1. 首頁 > 生活百科 > >

字符串 P7361 「JZOI-1」拜神

生活百科

題意： 給一個串，\(Q\) 次詢問區間 \([l,r]\) 中至少出現兩次的子串的最大長度 。
寫LCT是什么東東
以下做法很經典：
先求出 SA 以及 height 數組，然后按 height 從大到小每次加入一條連接 \(sa_i\) 與 \(sa_{i+1}\) 的邊，并用并查集維護每個連通塊 。這樣由經典結論 \(\mathrm{lcp}(i,j)=\min_{rank_i\le rank_k\le rank_j-1}\{height_k\}\) 可知，若已加的邊中 height 最小值為 \(k\)，那么 \(\mathrm{lcp}(i,j)\ge k\) 當且僅當 \(i,j\) 當前在同一連通塊內 。
在本題中，每次使用啟發式合并+可持久化線段樹維護每個 \(i\) 在連通塊中的后繼（即下一個比它大的），查詢時二分答案 \(L\)，看長度為 \(L\) 時是否有 \(\min_{i\le k\le j}suf_k\le r-L+1\) 即可 。
時間復雜度 \(O(n\log^2n)\) 。這玩意不好過LCT
【字符串 P7361 「JZOI-1」拜神】

    推薦閱讀