重复子串（string）

从\(ckw\)博客上看来的题目，可能是正睿oj上的，但我想我这样没有氪金的自然是写不了的，就口胡一波吧

题意：给定一个字符串，多组询问，每次询问一个子串的权值；一个字符串的权值定义为这个字符串里出现次数超过\(1\)次且长度最大的子串的长度，\(n,m\leq 100000\)

首先这个东西具有单调性，我们显然可以二分

对于一次询问\([l,r]\)，我们二分出来的长度是\(mid\)

如果\([l+mid-1,r]\)这个区间里有两个前缀的\(LCS\)长度大于\(mid\)我们就可以断定答案可以更大

所以我们现在需要求一个区间内两两\(LCS\)的最大值

这让我们想到了这道题

考虑到两个前缀\(LCS\)等于这两个前缀对应节点在\(parent\)树上的\(lca\)的\(len\)

于是我们启发式合并\(set\)，每次把一个\(set\)往另一个\(set\)里暴力插入得时候查一下前驱和后继，因为那些距离当前位置更远的显然不如前驱或者后继更优，更容易被计入答案；这样就得到了\(nlogn\)个形如\((l,r,v)\)的三元组，表示\(l\)前缀和\(r\)前缀的\(LCS\)是\(v\)

现在我们可以直接在树套树数点，复杂度高达\(4\)个\(log\)显然不可写，考虑离线

我们将所有三元组以及询问都按照右端点排序，我们显然可以保证在处理一个询问之前把所有右端点小于它的三元组的左端点都加入到一棵线段树里去

处理询问的时候二分长度去线段树上查左端点大于\(l-mid+1\)的最大值就好了

~~我应该没有胡错吧~~

巴特西

重复子串（string）

最新文章

热门文章