AT_abc328_c [ABC328C] Consecutive

题目描述

给定一个只由小写英文字母组成、长度为 $N$ 的字符串 $S = S_1S_2\ldots S_N$。

此外，还给定了 $Q$ 个关于 $S$ 的询问。对于 $i = 1, 2, \ldots, Q$，第 $i$ 个询问由两个整数 $l_i, r_i$ 表示，内容如下：

在 $S$ 的第 $l_i$ 个字符到第 $r_i$ 个字符组成的子串 $S_{l_i}S_{l_i+1}\ldots S_{r_i}$ 中，相同的小写英文字母相邻出现的次数是多少？也就是说，满足 $l_i \leq p \leq r_i-1$ 且 $S_p = S_{p+1}$ 的整数 $p$ 有多少个？

请输出每个询问的答案。

输入格式

输入按以下格式从标准输入中给出。

$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

输入 #1

11 4
mississippi
3 9
4 10
4 6
7 7

输出 #1

2
2
0
0

输入输出样例 #2

输入 #2

5 1
aaaaa
1 5

输出 #2

4

说明/提示

限制条件

• $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$。

样例解释 1

对于 $4$ 个询问的答案如下：

• 对于第 $1$ 个询问，$S_3S_4\ldots S_9 =$ ssissip，其中相同小写英文字母相邻出现的位置有 $S_3S_4 =$ ss 和 $S_6S_7 =$ ss，共 $2$ 个。
• 对于第 $2$ 个询问，$S_4S_5\ldots S_{10} =$ sissipp，其中相同小写英文字母相邻出现的位置有 $S_6S_7 =$ ss 和 $S_9S_{10} =$ pp，共 $2$ 个。
• 对于第 $3$ 个询问，$S_4S_5S_6 =$ sis，没有相同小写英文字母相邻出现，答案为 $0$。
• 对于第 $4$ 个询问，$S_7 =$ s，没有相同小写英文字母相邻出现，答案为 $0$。

样例解释 2

$S_1S_2\ldots S_5 =$ aaaaa，其中相同小写英文字母相邻出现的位置有 $S_1S_2 =$ aa、$S_2S_3 =$ aa、$S_3S_4 =$ aa、$S_4S_5 =$ aa，共 $4$ 个。

由 ChatGPT 4.1 翻译