P3732 [HAOI2017] Supply-side Reform

# Description You investigated the supply-demand balance of an industry over the past $ n $ periods. Each period is represented by a single digit, either $ 0 $ or $ 1 $. Thus, this forms a $ \texttt{01} $ string $ S $ of length $ n $. To better understand the data, you need to answer several queries. Let $ \text{data}(L, R) $ denote: among all suffixes of $ S $ whose starting positions lie in $ [L, R] $, the length of the longest common prefix of the two suffixes that achieve the maximum common prefix. For each query $ L, R $, compute: $$ ans = \sum_{L \leqslant i < R} \text{data}(i, R). $$ It is guaranteed that each character of $ S $ is randomly generated as $ 0 $ or $ 1 $.

你调查了某个产业近来 $n$ 个时期的供求关系平衡情况，每个时期的情况都用 $0$ 或 $1$ 中的一个数字来表示。于是这就是—个长度为 $n$ 的 $\texttt{01}$ 字符串 $S$。为了更好的了解这一些数据，你需要解决一些询问，我们令 $\text{data}(L,R)$ 表示：在字符串 $S$ 中，起始位置在 $[L,R]$ 之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。 对于每一个询问 $L,R$，求： $$ans = \sum_{L \leqslant i < R} \text{data}(i,R)$$ 数据范围保证，串 $S$ 中的每一位都是在 $0$ 和 $1$ 之间随机产生的。

第一行 $2$ 个整数 $n,Q$，表示字符串的长度，以及询问个数。 接下来一行长度为 $n$ 的一个 $\texttt{01}$ 串 $S$。 接下来 $Q$ 行，每行 $2$ 个整数 $L,R$，一个询问 $L,R$。

Output $ Q $ lines, each containing a single integer, the answer to the corresponding query.

[Constraints and Notes] | Data Point | Scale of $ n $ | Scale of $ Q $ | |:-:|:-:|:-:| | $1, 2$ | $ \leqslant 20 $ | $ \leqslant 20 $ | | $3, 4$ | $ \leqslant 100 $ | $ \leqslant 100 $ | | $5, 6$ | $ \leqslant 5 \times 10^3 $ | $ \leqslant 5 \times 10^3 $ | | $7, 8, 9, 10$ | $ \leqslant 10^5 $ | $ \leqslant 10^5 $ | For all testdata, it is guaranteed that $ n \leqslant 10^5 $, $ Q \leqslant 10^5 $, $ 1 \leqslant L < R \leqslant n $, and the $ \texttt{01} $ string is randomly generated. Translated by ChatGPT 5