题目简述：给定字符串$s[1 \dots n](n \leq 2 \times 10^5)$，以及$Q \leq 2 \times 10^5$个询问，每个询问有两个参数$1 \leq l \leq r \leq n$，求
$$ \sum_{i=l}^r \operatorname{lcp}(s[l \dots r], s[i \dots r]), $$
其中$\operatorname{lcp}(s, t)$表示字符串$s$和$t$的最长公共前缀（Longest Common Prefix）的长度。
模型转化
$$ \sum_{i=l}^r \operatorname{lcp}(s[l \dots r], s[i \dots r]) = \sum_{i=l}^r \min\{\operatorname{lcp}(s[l \dots n], s[i \dots n]), r-l+1\} $$
后缀自动机学习资料：
1. CSDN
2. SAISUMIT
3. CodeForces
后缀树学习资料：
1. cnblogs
为了方便起见，我们在这里再次简要申明后缀自动机和后缀树的定义，以防止混淆各种不同定义的细微差别。
原文：https://www.cnblogs.com/TinyWong/p/10363110.html