对于这种询问区间本质不同的元素个数，我们通常有以下两种方案：
- 记 \(pre_x\) 为 \(x\) 之前最靠后的一个与其本质相同的元素的位置，可以转化为偏序问题。
- 扫描线，每遇到一个元素，就在该位置 \(+1\)，在上一个本质相同元素处 \(-1\)，询问区间和。
可以发现，前一种统计的是第一个元素，后一种统计的是最后一个（然而没什么用）。
我们将本质不同的子串视为元素，它是一堆区间。我们可以考虑使用类似第二种方法统计答案。
每次扫到一个新的位置 \(i\)，遇到的元素即以该位置结尾的所有子串，这在 parent tree 上是一条链，我们把它们的“最后一次出现位置”改为 \(i\)，然后再减掉一些贡献。
发现这个有颜色段均摊的形式。我们树剖之后，每次修改最多增加 \(O(\log n)\) 个颜色段，因此一共只有 \(O(n\log n)\) 次颜色段修改。一次颜色段的修改容易表示成区间加减的形式。
那么这个题就做完了，复杂度 \(O(n\log^2n+q\log n)\)。