Ж-function
Contest: Codeforces Round 530 (Div. 1)
Difficulty rating: 3500
Tags: string suffix structures, strings

The length of the longest common prefix of two strings $$$s=s_1 s_2 \ldots s_n$$$ and $$$t = t_1 t_2 \ldots t_m$$$ is defined as the maximum $$$k \le \min(n, m)$$$ such that $$$s_1 s_2 \ldots s_k$$$ equals $$$t_1 t_2 \ldots t_k$$$. Let's denote the longest common prefix of two strings $$$s$$$ and $$$t$$$ as $$$lcp(s,t)$$$.

Z-function of a string $$$s_1 s_2 \dots s_n$$$ is a sequence of integers $$$z_1, z_2, \ldots, z_n$$$, where $$$z_i = lcp(s_1 s_2 \ldots s_n,\ \ s_i s_{i+1} \dots s_n)$$$. Ж-function of a string $$$s$$$ is defined as $$$z_1 + z_2 + \ldots + z_n$$$.

You're given a string $$$s=s_1 s_2 \ldots s_n$$$ and $$$q$$$ queries. Each query is described by two integers $$$l_i$$$ and $$$r_i$$$, where $$$1 \le l_i \le r_i \le n$$$. The answer for the query is defined as Ж-function of the string $$$s_{l_i} s_{l_i +1} \ldots s_{r_i}$$$.

Input format:
The first line contains the string $$$s$$$, consisting of lowercase English letters ($$$1 \leq |s| \leq 200\,000$$$). The second line contains one integer $$$q$$$ — the number of queries ($$$1 \leq q \leq 200\,000$$$). Each of the following $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$, describing the query ($$$1 \leq l_i \leq r_i \leq |s|$$$).

Output format:
For every query output one integer: the value of Ж-function of the corresponding substring.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
In the first sample case there are four queries:

- the first query corresponds to the substring bb, and its Ж-function equals $$$2 + 1 = 3$$$;
- the second query corresponds to the substring abb, and its Ж-function equals $$$3 + 0 + 0 = 3$$$;
- the third query corresponds to the substring b, and its Ж-function equals $$$1$$$.
- the fourth query corresponds to the substring abdd, and its Ж-function equals $$$4 + 0 + 0 + 0= 4$$$.

Example input:
abbd
4
2 3
1 3
3 3
1 4

Example output:
3
3
1
4

Example input:
bbaaa
5
2 4
1 5
1 5
3 3
1 2

Example output:
3
6
6
1
3

Editorial:
Answer for query $$$l$$$, $$$r$$$ is equal to $$$\sum^{r}_{i=l}{\min(lcp(l,i), r - i + 1)}$$$. $$$lcp(i, l)$$$ is the length of longest common preffix of $$$i$$$-th and $$$l$$$-th suffixes. Let $$$\min(lcp(l,i), r - i + 1)$$$ be denoted by «cutted $$$lcp$$$» of two suffixes. Now we can use another approach to calculate the answer. For each $$$k = 1 \ldots r - l + 1$$$ let's count number of suffixes $$$i = l \ldots r$$$ with «cutted $$$lcp$$$» $$$\geq k$$$, it is equal to number of suffixes $$$i = l \ldots r - k + 1$$$ with $$$lcp$$$ $$$\geq k$$$. The sum of these values will be an answer.
Let's build the suffix tree of our string.
To count this value for fixed $$$k$$$ and $$$l$$$, let's consider an ancestor of $$$l$$$-th suffix with depth equal to $$$k$$$, number of sought for suffixes is equal to a number of suffixes with numbers from $$$l$$$ to $$$r - k + 1$$$ in the subtree of our vertex.
So let's suppose that for each vertex $$$v$$$ there is a data structre, which can count number of leaves with numbers from $$$l$$$ to $$$r-h_v+1$$$ ($$$h_v$$$ is the depth of $$$v$$$) in subtree of $$$v$$$ for fixed $$$l$$$ and $$$r$$$.
Now to get an answer for query we should find sum of these sums for given $$$l$$$ and $$$r$$$ for all ancestors with depth $$$\leq r - l + 1$$$ of vertex which corresponds the substring of request.
Now we can just divide the request into two parts! We should count the number of leaves with numbers $$$\leq r - h_v + 1$$$ and number of leaves with numbers $$$< l$$$.
The first part is similar to counting number of leaves (in subtree) with numbers $$$x$$$, that $$$x + h_v \leq r + 1$$$.
Now we should use Heavy-light decompositin of our suffix tree to find sum on way. Let's consider all $$$\mathcal{O}(\log n)$$$ heavy ways which are above the fixed leaf. Our vertex appears in some prefixes of these ways, and its values are $$$x+h_v, x+h_v + 1, \ldots, x+h_v+len$$$. So on each way there are some leaves determined by ($$$x + h_v, len$$$) which should be considered. Lets denote these pairs by ($$$x_i, y_i$$$). Now we just need to count number of $$$(i, j)$$$, that $$$0 \leq j \leq y_i$$$ and $$$x_i + j \leq r + 1$$$. I.e. for each query we should calculate $$$\sum{\max(0, \min(r + 1 - x_i, y_j))}$$$ on prefixes of considered heavy ways.
Now we can use scaning line and Fenwick tree for each way to process all queries. It would be easy for you to find out how to do it if you understood everything before ;).
The second part can be done similary, but in this case each leaf corresponds a point, not linear function.
The complexity is $$$\mathcal{O}(n \log^2 n)$$$, which easily passes TL.