简要题意：每次询问 \([l,r]\)，求 \(S\) 的子串 \(t\) 满足 \(t^{\infty}<S[l:r]^{\infty}\) 的本质不同子串 \(t\) 个数。
设 \(s=S[l:r]\) 即询问串。
我们把贡献分成多个部分统计。
先统计掉所有满足 \(t<s^{\infty}\) 的串（即将 \(t\) 重复一次后就出现小于的情况）。
可以先做后缀排序，然后在后缀数组上二分 \(s^{\infty}\) 的位置，把在这个位置之前且不为 \(s\) 前缀的所有串计入答案。二分需要比较，比较只需要求 \(s^{\infty}\) 和某个后缀的 LCP，可以求两次 LCP 来实现。
剩下情况要统计 \(t=s^k a\)，其中 \(k\ge 0\) 且 \(a\) 为 \(s\) 的一个前缀。
任意一个 \(t=s^k a\) 的情况都能等价成 \(t=a\) 的情况。首先要求一下 \(s^{\infty}\) 在原串中能匹配最长的前缀长度（来计算每个 \(a\) 有多少个 \(t\)），由于之前在后缀数组上二分了 \(s^{\infty}\) 的位置，这个就不难求出。
然后考虑 \(s\) 每个前缀 \(a\) 在怎样的条件下符合。
设 \(s=ab\)，考虑比较 \(s^{\infty}\) 和 \(a^{\infty}\) 的过程，先把两个串开头的 \(a\) 消掉，然后发现就是求 \(s\) 和 \(b\) 的 LCP 的过程（如果 \(s\) 和 \(b\) 又匹配了一个 \(a\) 的长度，那就是又消掉了一个 \(a\) 继续匹配）。
如果 \(b\) 不是 \(s\) 的前缀，那 \(s\) 匹配 \(b\) 就会在某个位置出现不同，也就是要求 \(b<s\)。于是先二分一下 \(s\) 在原串后缀数组中的位置，求符合条件的 \(b\) 就是一个二维数点（初始位置在一个区间内，字典序在一个前缀内）。
如果 \(b\) 是 \(s\) 的前缀，那说明 \(a\) 是 \(s\) 的一个周期。
考虑用基本子串字典求出每个 border group，也就求出了每个周期 group，在每个 group 中都满足 \(a=A,AB,ABB,ABBB..\) 的形式。
考虑一个性质，\(A^{\infty},(AB)^{\infty},(ABB)^{\infty}..\) 的字典序是单调的。于是可以二分一个位置，使得其中一半的串满足 \(a^{\infty}<s^{\infty}\)，只需要做比较操作。