【北大集训2021】扑克比大小

· · 题解

简要题意：每次询问 [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