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$ 个询问的答案。

限制条件

• $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 翻译