← 返回题目列表

AtCoder · abc328_c

F. 连续

中文机器翻译题面 查看原题

分数: 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.