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

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

题目描述

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

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

给定一个长度为 nn 的仅由数字构成的字符串 SS,现在有 qq 次询问,第 kk 次询问会给出 SS 的一个字符串 Sl,rS_{l,r} ,请你求出有多少对 (i,j)(i, j),满足 1i<jn1 \le i < j \le ni+1<ji + 1 \lt j,且 Sl,rS_{l,r} 出现在 S1,iS_{1,i} 中或 Si+1,j1S_{i+1, j−1} 中或 Sj,nS_{j,n} 中。

输入格式

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

输出格式

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

样例

样例 1 输入

5 2
00100
1 2
1 3

样例 1 输出

5
1

数据范围与提示

测试点 n q 其它约定
11 =50=50 =100=100
232 \sim 3 =300=300 =300=300
454 \sim 5 =2000=2000 =3000=3000
696 \sim 9 =100000=100000 =100000=100000 Sl,r106\sum \lvert S_{l,r} \rvert \le 10^6
101210 \sim 12 =30000=30000 =50000=50000
1313 =100000=100000 =100000=100000 SS 中只有 00
142014 \sim 20 =100000=100000 =300000=300000

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