背景

线下选手，懒得再打一遍代码了。

镜像赛竟然只有三个人过，让我非常吃惊。

题解

由于字符串保证随机生成，考虑通过取每个后缀一定长度的前缀预存储来加快比对速度。

对于一个长度为 的字符串 ，可以为其确定唯一的标识值 ，使得字典序更大的字符串拥有更大的标识值。

维护序列 ，其中 。我们需要对这个数组求前缀和，所以使用树状数组。

维护集合序列 ，其中 。在前 个字符无法确定顺序要用到它进行补充。

修改时直接枚举 前 个起始位置暴力更新。

查询时在 上先找前 个字符比这个后缀小的位置的数量，然后对于前 个字符相同的枚举 内的元素暴力比对即可。

时间复杂度 ，赛时取 ，可以通过。