CF1098F.Ж-function

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}$.

两个字符串 $s=s_1 s_2 \ldots s_n$ 与 $t = t_1 t_2 \ldots t_m$ 的最长公共前缀长度定义为最大的整数 $k \le \min(n, m)$，使得 $s_1 s_2 \ldots s_k = t_1 t_2 \ldots t_k$。我们记字符串 $s$ 与 $t$ 的最长公共前缀为 $lcp(s,t)$。

字符串 $s_1 s_2 \dots s_n$ 的 Z-函数 是一个整数序列 $z_1, z_2, \ldots, z_n$，其中 $z_i = lcp(s_1 s_2 \ldots s_n,\ \ s_i s_{i+1} \dots s_n)$。字符串 $s$ 的 Ж-函数 定义为 $z_1 + z_2 + \ldots + z_n$。

给定一个字符串 $s=s_1 s_2 \ldots s_n$ 和 $q$ 个查询。每个查询由两个整数 $l_i$ 和 $r_i$ 描述，满足 $1 \le l_i \le r_i \le n$。该查询的答案定义为子串 $s_{l_i} s_{l_i +1} \ldots s_{r_i}$ 的 Ж-函数值。

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|$).

第一行包含字符串 $s$，由小写英文字母组成（$1 \leq |s| \leq 200\,000$）。第二行包含一个整数 $q$ —— 查询次数（$1 \leq q \leq 200\,000$）。接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$，描述一次查询（$1 \leq l_i \leq r_i \leq |s|$）。

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

对于每个查询，输出一个整数：对应子串的 Ж 函数值。

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$.

在第一个样例中，共有四个查询：

• 第一个查询对应子串 bb，其 Ж-函数值为 $2 + 1 = 3$；
• 第二个查询对应子串 abb，其 Ж-函数值为 $3 + 0 + 0 = 3$；
• 第三个查询对应子串 b，其 Ж-函数值为 $1$；
• 第四个查询对应子串 abdd，其 Ж-函数值为 $4 + 0 + 0 + 0 = 4$。