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