CF587F SA 单根号做法。

· · 题解

人傻常数大。

本文默认 \mathcal{O}(n)=\mathcal{O}(m)=\mathcal{O}\left(\sum\limits_{i=1}^n|s_i|\right)。

众所周知，此题题解区已经有了 \mathcal{O}\left(n\sqrt{n\log n}\right) 的 SA 做法和 \mathcal{O}(n\sqrt{n}) 的 SAM / ACAM 做法。那么 SA 能否做到 \mathcal{O}(n\sqrt{n}) 呢？答案显然是可以的。上述复杂度讨论的均是时间。

首先将全部询问离线，维护一个前缀中的串在某个串中的出现次数。将所有串拼成大串 S 进行后缀排序。此时 \mathcal{O}(|S|)=\mathcal{O}(n)。

我们可以将在一个字符串中出现转化为在一个后缀作为前缀出现。当 i 加进前缀的时候，可以找到以它为前缀的所有后缀。这样的后缀排名形如一个区间 [L,R]，则排名在这个区间内的后缀出现次数都要加 1。

串长一定时可以阈值分治。设阈值为 B。则对于 s_k 长度不超过 B 询问，可以直接暴力枚举那个串的后缀，设查询的时间复杂度为 \mathcal{O}(Q_1(n))，则这部分可以做到 \mathcal{O}(B\cdot Q_1(n))。

对于 s_k 长度大于 B 的询问，显然不能使用上述查询方式。此时询问的串 s_k 只有 \mathcal{O}\left(\dfrac{n}{B}\right) 种。考虑对于这些串单独计算答案，则 s_i 在 s_k 中出现的次数相当于在 s_k 的后缀排名集合中查询 [L,R] 内的数的个数。设查询的时间复杂度为 \mathcal{O}(Q_2(n))，则这部分的时间复杂度为 \mathcal{O}\left(\dfrac{n}{B}Q_2(n)\right)。

考虑使用分块解决。对于小串，使用 \mathcal{O}(\sqrt{n}) 区间加、\mathcal{O}(1) 单点查询的分块解决。

对于大串，每个都用分块维护一个值域前缀和表示集合中不超过某个值的元素个数，那么对于这个大串排名集合中的一个元素，它产生的影响是一段后缀的值域前缀和加 1。到了查询的时候，直接单点查询 R 和 L-1 位置上的信息即可。同样使用 \mathcal{O}(\sqrt{n}) 区间加、\mathcal{O}(1) 单点查询的分块解决。

注意此时空间复杂度为 \mathcal{O}\left(\dfrac{n^2}{B}\right)。

此时，取 B=\mathcal{O}(\sqrt{n})，可以做到 \mathcal{O}(n\sqrt{n}) 的时空复杂度。但是空间开不下，因此取了个比较接近的，复杂度不变，会带一个较大的常数。结果是没跑过 \mathcal{O}(n\sqrt{n}\log n)。。。

\mathcal{O}(n\sqrt{n}) Code

\mathcal{O}(n\sqrt{n}\log n) Code