题解

思路

小范围直接按定义去重；中等范围对每次询问构造后缀数组；满分范围固定左端点增量构建后缀自动机，并预处理所有区间答案。

做法

子任务一

询问区间很短时，可以枚举区间内每一个子字符串，把它们放入集合中去重。集合大小就是答案。这个方法直接对应定义，适合验证其他算法在小规模输入上的正确性。

子任务二

对每次询问单独构造区间字符串的后缀数组和高度数组。长度为 $m$ 的字符串共有 $m(m+1)/2$ 个带位置的子字符串。按字典序排列所有后缀后，重复的部分恰好由相邻后缀的最长公共前缀贡献，因此答案为

$$\frac{m(m+1)}2-\sum_{i=2}^{m}\operatorname{LCP}(\operatorname{SA}_{i-1},\operatorname{SA}_i).$$

使用倍增法构造后缀数组，一次询问的时间复杂度为 $O(m\log^2 m)$，空间复杂度为 $O(m)$。这一方法适合中等长度和询问数。

子任务三

询问次数较多时，不能为每次询问重复建立自动机。固定左端点 $l$，从空串开始依次加入 $s_l,s_{l+1},\ldots,s_n$。当右端点扩展到 $r$ 时，自动机恰好表示 $s[l\ldots r]$ 的全部子字符串，因此当前累计贡献就是 $f(s[l\ldots r])$。

对每个左端点各执行一次上述过程，并将所有答案预处理到二维表中。之后每次询问只需查表。

正确性证明

后缀自动机的每个状态表示一组结束位置集合相同的子字符串。状态 $u$ 对应的子字符串长度恰为

$$\operatorname{len}(\operatorname{link}(u))+1, \operatorname{len}(\operatorname{link}(u))+2, \ldots, \operatorname{len}(u),$$

所以该状态贡献 $\operatorname{len}(u)-\operatorname{len}(\operatorname{link}(u))$ 个不同子字符串。不同状态表示的集合互不重复，因此所有状态贡献之和等于当前字符串中不同子字符串的总数。

固定 $l$ 后，每加入一个字符 $s_r$，自动机表示的字符串正是 $s[l\ldots r]$。由上面的计数结论，记录的累计贡献等于 $f(s[l\ldots r])$。遍历所有左端点后，二维表包含每个合法区间的正确答案，故查表回答每次询问也是正确的。

复杂度分析

每次扩展后缀自动机的均摊复杂度为 $O(|\Sigma|)$；字符集大小固定时可视为常数。所有左端点对应的扩展总数为 $O(n^2)$，预处理时间复杂度为 $O(n^2|\Sigma|)$，空间复杂度为 $O(n^2+n|\Sigma|)$。每次询问的时间复杂度为 $O(1)$。