rt

给定一个长度为 $n$ 的串 $S$。

定义 $\text{occ}(T)$ 表示串 $T$ 在 $S$ 中的出现次数。

$q$ 次询问，每次询问给定一个区间 $[l,r]$，查询 $S[l:r]$ 的所有子串的 $\text{occ}$ 之和。