分数: 300 点
问题陈述
给你一个字符串 S = S_1S_2\ldots S_N 长度 N 由小写英文字母组成。
此外,您还获得 Q 有关字符串的查询 S。 对于 i = 1, 2, \ldots, Q, i-第一个查询由两个整数表示 l_i, r_i 并询问以下问题。
在子字符串中 S_{l_i}S_{l_i+1}\ldots S_{r_i} of S,范围从 l_i-第 r_i第一个字符,有多少处相同的小写英文字母连续出现两次? 换句话说,有多少个整数 p 满足 l_i \leq p \leq r_i-1 和 S_p = S_{p+1}?
打印每个问题的答案 Q 查询。
约束
- N 和 Q 是整数。
- 1 \leq N, Q \leq 3 \times 10^5
- S 是一个长度为的字符串 N 由小写英文字母组成。
- l_i 和 r_i 是整数。
- 1 \leq l_i \leq r_i \leq N
输入
输入由标准输入按以下格式给出:
N Q S l_1 r_1 l_2 r_2 \vdots l_Q r_Q
输出
打印 Q 行。 对于 i = 1, 2, \ldots, Q, i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
11 4 mississippi 3 9 4 10 4 6 7 7
示例输出 1
2 2 0 0
四个疑问的答案如下。
- 对于第一个查询, S_3S_4\ldots S_9 =
ssissip有两个地方相同的小写英文字母连续出现两次: S_3S_4 =ss和 S_6S_7 =ss. - 对于第二个查询, S_4S_5\ldots S_{10} =
sissipp有两个地方相同的小写英文字母连续出现两次: S_6S_7 =ss和 S_9S_{10} =pp. - 对于第三个查询, S_4S_5S_6 =
sis中相同的小写英文字母连续出现两次的位置为零。 - 对于第四个查询, S_7 =
s中相同的小写英文字母连续出现两次的位置为零。
示例输入 2
5 1 aaaaa 1 5
示例输出 2
4
S_1S_2\ldots S_5 = aaaaa 有四个地方相同的小写英文字母连续出现两次:
S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa,和 S_4S_5 = aa.