#2479. 「九省联考 2018」制胡窜

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

题目描述

对于一个字符串 S ,我们定义 |S| 表示 S 的长度。

接着,我们定义 S_i 表示 S 中第 i 个字符, S_{L,R} 表示由 S 中从左往右数,第 L 个字符到第 R 个字符依次连接形成的字符串。特别的,如果 L > R ,或者 L < [1, |S|] , 或者 R < [1, |S|] 我们可以认为 S_{L,R} 为空串。

给定一个长度为 n 的仅由数字构成的字符串 S ,现在有 q 次询问,第 k 次询问会给出 S 的一个字符串 S_{l,r} ,请你求出有多少对 (i, j) ,满足 1 \le i < j \le n i + 1 \lt j ,且 S_{l,r} 出现在 S_{1,i} 中或 S_{i+1, j−1} 中或 S_{j,n} 中。

输入格式

输入的第一行包含两个整数 n, q 。 第二行包含一个长度为 n 的仅由数字构成的字符串 S 。 接下来 q 行,每行两个正整数 l r ,表示此次询问的子串是 S_{l,r}

输出格式

对于每个询问,输出一个整数表示合法的数对个数。

样例

样例 1 输入

5 2
00100
1 2
1 3

样例 1 输出

5
1

数据范围与提示

测试点 n q 其它约定
1 =50 =100
2 \sim 3 =300
4 \sim 5 =2000 =3000
6 \sim 9 =100000 \sum \lvert S_{l,r} \rvert \le 10^6
10 \sim 12 =30000 =50000
13 =100000 =100000 S 中只有 0
14 \sim 20 =300000

对于所有测试数据, 1 \le n \le 10^5 1 \le q \le 3 · 10^5 1 \le l \le r \le n