P3732 [HAOI2017] 供给侧改革

题目描述

你调查了某个产业近来 $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$ 之间随机产生的。

输入格式

输出格式

说明/提示

【数据规模与约定】 |数据点|$n$ 的规模|$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$| 对于所有的数据保证:$n \leqslant 10^5$,$Q \leqslant 10^5$,$1 \leqslant L < R \leqslant n$,$\texttt{01}$ 串随机生成。