CF1098F Ж-function

两个字符串 $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$。我们用 $lcp(s, t)$ 表示字符串 $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)$。Ж 函数定义为 $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}$ 的 Ж 函数值。

第一行输入一个仅包含小写英文字母的字符串 $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|$）。

对于每个询问，输出一个整数，表示对应子串的 Ж 函数值。

在第一个样例中有四个询问： - 第一个询问对应子串 bb，其 Ж 函数为 $2 + 1 = 3$； - 第二个询问对应子串 abb，其 Ж 函数为 $3 + 0 + 0 = 3$； - 第三个询问对应子串 b，其 Ж 函数为 $1$； - 第四个询问对应子串 abdd，其 Ж 函数为 $4 + 0 + 0 + 0 = 4$。 由 ChatGPT 4.1 翻译