不会字符串科技/ll

设根号分治的阈值为 $T$，先预处理出整串哈希，然后对于长度 $>T$ 的串最多只会询问 $\frac{n}{T}$ 次，这部分时间复杂度为 $\mathcal{O}(\frac{n^2}{T})$；对于 $\leq T$ 的串，先预处理原串中所有长度 $\leq T$ 的哈希值，扔到 $T$ 个桶里排序，每次询问直接二分桶里有几个当前值，这部分预处理时间复杂度 $\mathcal{O}(Tn\log n)$，询问复杂度 $\mathcal{O}(q\log n)$。列均值等式解得 $T≈\sqrt{\frac{n}{\log n}}$，总复杂度为 $\mathcal{O}(n\sqrt{n\log n})$。

感觉做法复杂度是没问题的，3s 时限按理很充足了，但不知道是阈值算错还是被卡常的缘故一直 TLE 10 个点，link；并且把 $T$ 设为 $\frac{\sqrt{q}}{\log n}$ 时反而 T 得更少，求调 / 帮分析复杂度。