P6292 Number of Essentially Different Substrings in an Interval.

Given a string $S$ of length $n$ consisting only of lowercase letters, there are $m$ queries. Each query asks how many essentially different non-empty substrings are contained in the string formed by the $L$-th to the $R$-th characters of $S$. Two strings $a, b$ are defined to be the same if and only if $|a|=|b|$ and for all $i\in[1,|a|]$, we have $a_i=b_i$.

The first line contains a string $S$ of length $n$. The second line contains an integer $m$, indicating the number of queries. The next $m$ lines each contain two integers $l_i, r_i$, describing the $i$-th query.

Output $m$ lines, each containing an integer, representing the answer to the $i$-th query.

#### Explanation for Sample 1 - For the first query, the string is $\texttt{aa}$, and it contains $\texttt{a}$ and $\texttt{aa}$, for a total of $2$ essentially different substrings. - For the second query, the string is $\texttt{aba}$, and it contains $\texttt{a},\texttt{b},\texttt{ab},\texttt{ba},\texttt{aba}$, for a total of $5$ essentially different substrings. - For the third query, the string is $\texttt{babc}$, and it contains $\texttt{a}$,$\texttt{b}$,$\texttt{c}$,$\texttt{ab}$,$\texttt{ba}$,$\texttt{bc}$,$\texttt{bab}$,$\texttt{abc}$,$\texttt{babc}$, for a total of $9$ essentially different substrings. #### Constraints - For $20\%$ of the testdata, $n\leq 3\times 10^3$ and $m\leq 3\times 10^3$. - For $100\%$ of the testdata, $1\leq n\leq 10^5$, $1\leq m\leq 2\times 10^5$, $1\leq l_i\leq r_i\leq n(i\in[1,m])$. Translated by ChatGPT 5