5
P7361 「JZOI-1」拜神 （字符串） - CharlieVinnie
source link: https://www.cnblogs.com/Charlie-Vinnie/p/16756641.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
P7361 「JZOI-1」拜神 （字符串）
题意： 给一个串，QQ 次询问区间 [l,r][l,r] 中至少出现两次的子串的最大长度。
写LCT是什么东东
以下做法很经典：
先求出 SA 以及 height 数组，然后按 height 从大到小每次加入一条连接 saisai 与 sai+1sai+1 的边，并用并查集维护每个连通块。
这样由经典结论 lcp(i,j)=minranki≤rankk≤rankj−1{heightk}lcp(i,j)=minranki≤rankk≤rankj−1{heightk} 可知，若已加的边中 height 最小值为 kk，那么 lcp(i,j)≥klcp(i,j)≥k 当且仅当 i,ji,j 当前在同一连通块内。
在本题中，每次使用启发式合并+可持久化线段树维护每个 ii 在连通块中的后继（即下一个比它大的），查询时二分答案 LL，看长度为 LL 时是否有 mini≤k≤jsufk≤r−L+1mini≤k≤jsufk≤r−L+1 即可。
时间复杂度 O(nlog2n)O(nlog2n)。这玩意不好过LCT
本文作者：CharlieVinnie
本文链接：https://www.cnblogs.com/Charlie-Vinnie/p/16756641.html
版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK