view in my cnblogs.

两年前的我这么强吗，还会写 30pts，现在的我 30pts 都写不出来。这种字符串工业太可怕了！

好吧，其实做法的提示性很强，这个东西明摆着是让你根号分治的。难点在于维护而不在于贪心。

我先口胡一个东西看看对不对啊。跑 SA，设阈值是 $B$，然后 $\gt B$ 的直接二分出来 $\rm sa$ 范围，然后扔主席树上不停进行区间查询时间复杂度是 $\mathcal O(\frac{nq}{B}\log n)$ 的一个东西。然后 $\le B$ 的子串只有 $\Theta(nB)$ 个。怎么预处理来着？

哦好像题目里规定了 $\le B$ 的很少，$r-l$ 随机均匀这个性质咋用？是想告诉我默认 $\tilde O(r-l)=1000$ 吗？

那我是不是还是可以和上面那个东西一样暴力跑啊 /qd。

看一眼 myee 的题解，好像还真行，$X=50,Y=2000$ 的话这个东西的复杂度就是

$$\mathcal O(\frac{\log n}{Y-X}\int_X^Y \frac{n}{x}\, \mathrm d x) = \mathcal O(n\log n\frac{\ln Y - \ln X}{Y-X})$$

我不会微积分啊，这个式子是抄的。写完这个一定要学一学微积分，要不然这种细致复杂度分析不会做 /ng。（学不会，开摆）

好像还有 $r-l\le X$ 的情况，这个咋办来着。

一般来说字符串这种东西可以反着来，想一想出题人会怎么卡。他要卡我的话肯定能匹配的越多越好，那这样的话询问的本质不同串是不是不会多。

看题解。好吧，首先按上面的方法找到第一个位置，然后倍增预处理就行。不想写代码，啥时候闲的蛋疼了再写。