自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:44:24，当前版本为作者最后更新于2023-12-05 22:37:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意：每次询问 $[l,r]$，求 $S$ 的子串 $t$ 满足 $t^{\infty}<S[l:r]^{\infty}$ 的本质不同子串 $t$ 个数。

设 $s=S[l:r]$ 即询问串。

我们把贡献分成多个部分统计。

先统计掉所有满足 $t<s^{\infty}$ 的串（即将 $t$ 重复一次后就出现小于的情况）。

可以先做后缀排序，然后在后缀数组上二分 $s^{\infty}$ 的位置，把在这个位置之前且不为 $s$ 前缀的所有串计入答案。二分需要比较，比较只需要求 $s^{\infty}$ 和某个后缀的 LCP，可以求两次 LCP 来实现。

剩下情况要统计 $t=s^k a$，其中 $k\ge 0$ 且 $a$ 为 $s$ 的一个前缀。

任意一个 $t=s^k a$ 的情况都能等价成 $t=a$ 的情况。首先要求一下 $s^{\infty}$ 在原串中能匹配最长的前缀长度（来计算每个 $a$ 有多少个 $t$），由于之前在后缀数组上二分了 $s^{\infty}$ 的位置，这个就不难求出。

然后考虑 $s$ 每个前缀 $a$ 在怎样的条件下符合。

设 $s=ab$，考虑比较 $s^{\infty}$ 和 $a^{\infty}$ 的过程，先把两个串开头的 $a$ 消掉，然后发现就是求 $b$ 和 $s$ 的 LCP 的过程（如果 $s$ 和 $b$ 又匹配了一个 $a$ 的长度，那就是又消掉了一个 $a$ 继续匹配，并且接下来也是 $a$，所以相当于匹配 $a^{\infty}$。

那我们把比较 $s^{\infty}$ 和 $a^{\infty}$ 转化成了比较 $bs^{\infty}$（对应 $s^{\infty}$） 和 $s^{\infty}$（对应 $a^{\infty}$）。

继续讨论下一步匹配：

如果 $b$ 不是 $s$ 的前缀，那 $s$ 匹配 $b$ 就会在某个位置出现不同，也就是要求 $s<b$。于是先二分一下 $s$ 在原串后缀数组中的位置，求符合条件的 $b$ 就是一个二维数点（开始位置在一个区间内，字典序在一个后缀内）。当然这里二维数点完后，要容斥减去所有 $b$ 是 $s$ 的前缀的错误贡献，这个等下会解释做法。

如果 $b$ 是 $s$ 的前缀，那说明 $a$ 是 $s$ 的一个周期，$b$ 是 $s$ 的一个 border。

接下来设 $s=b+c$，那转化成了比较 $s^{\infty}$（对应 $s^{\infty}$）和 $cs^{\infty}$（对应 $a^{\infty}$）。

如果 $c=a,s=b+a$，那么 $a$ 也是 $s$ 的一个 border，此时发现会无限匹配，那不用计入答案，也不需要考虑之后的匹配了！

如果 $c\ne a$，那么会在比较 $a$ 和 $c$ 的时候得到结果，如果 $a>c$ 则会计入答案。

（省流：只要比较往后的一个 $s$ 的循环节是否正确，如果正确就无限匹配了，不会计入答案；如果错误就可以计算答案）

在特殊性质 A 下，能在串中找到一个开头包含了 $ss$ 的后缀起始位置。把询问串的位置移到这里，直接用上文的二维数点，那贡献就是对的了。

如果没有特殊性质，假设 $s$ 所在位置后缀的开头是 $st$（$t = [r:n]$）。那直接二维数点的话，对于所有 border $b$，就是在拿 $bt$ 和 $s$ 比较，这个贡献是错误的。

那就先减去 $bt$ 和 $s$ 比较的错误贡献，再加上 $bt$ 和 $s$ 比较的正确贡献。下面是对于所有 border $b$ 算贡献的方法：

用基本子串字典求出每个 border group，在每个 group 中都满足 $b=A,AB,ABB,ABBB,\dots$ 的形式。

考虑一个性质，$(A)t,(AB)t,(ABB)t,(ABBB)t,\dots$ 的字典序是单调的。于是可以二分一个位置，使得其中一半的串满足条件。只需要做比较操作，也就是 LCP 操作。

时间复杂度 $O(n\log n+q\log^2 n)$，瓶颈在最后一部分的 $\log$ 次二分以及基本子串字典的查询。

Code on uoj