#2313. 「HAOI2017」供给侧改革

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: __stdcall

题目描述

Anihc 国提高社会生产力水平,落实好以人民为中心的发展思想。决定进行供给侧结构性改革。

为了提高供给品质,你调查了某个产业近来 n 个时期的供求关系平衡情况,每个时期的情况都用 0 1 中的一个数字来表示,于是这就是—个长度为 n 01 字符串 S 。为了更好的了解这一些数据,你需要解决一些询问,我们令 \operatorname{data}(l,r) 表示:在字符串 S 中,起始位置在 [l,r] 之间的这些后缀之中,具有最长公共前缀的两个后缀的最长公共前缀的长度。

对于每一个询问 L , R 。求

\mathit{ans} = \sum\limits_{ L \le i \lt R } \operatorname{data}(i, R)

由于你其实根本没有时间调查,所以这些数据都是乱编的,即串 S 中的每一位都是在 0 1 之间随机产生的。

输入格式

第一行 2 个整数 n Q ,表示字符串的长度,以及询问个数。

接下来一行长度为 n 的一个 01 S

接下来 Q 行,每行 2 个整数 L,R ,一个询问 L.R

输出格式

Q 行,每行一个整数,表示对应询问的答案。

样例

样例输入

6 3
010110
2 5
1 6
1 2

样例输出

4
6
0

数据范围与提示

数据点 n 的规模 Q 的规模
1 n \leq 20 Q \leq 20
2 Q \leq 20
3 n \leq 100 Q \leq 100
4 Q \leq 100
5 n \leq 5000 Q \leq 5000
6 Q \leq 5000
7 n \leq 100000 Q \leq 100000
8 Q \leq 100000
9
10 Q \leq 100000

对于所有的数据保证: n \leq 100000 Q\leq 100000 1\leq L<R\leq n 01 串随机生成。