103282: [Atcoder]ABC328 C - Consecutive

Problem Statement

You are given a string $S = S_1S_2\ldots S_N$ of length $N$ consisting of lowercase English letters.

Additionally, you are given $Q$ queries about the string $S$. For $i = 1, 2, \ldots, Q$, the $i$-th query is represented by two integers $l_i, r_i$ and asks the following.

In the substring $S_{l_i}S_{l_i+1}\ldots S_{r_i}$ of $S$, which ranges from the $l_i$-th to the $r_i$-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers $p$ satisfy $l_i \leq p \leq r_i-1$ and $S_p = S_{p+1}$?

Print the answer for each of the $Q$ queries.

Constraints

• $N$ and $Q$ are integers.
• $1 \leq N, Q \leq 3 \times 10^5$
• $S$ is a string of length $N$ consisting of lowercase English letters.
• $l_i$ and $r_i$ are integers.
• $1 \leq l_i \leq r_i \leq N$

Input

The input is given from Standard Input in the following format:

$N$ $Q$
$S$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

Output

Print $Q$ lines. For $i = 1, 2, \ldots, Q$, the $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

2
2
0
0

The answers to the four queries are as follows.

• For the first query, $S_3S_4\ldots S_9 = $ ssissip has two places where the same lowercase English letter occurs twice in a row: $S_3S_4 = $ ss and $S_6S_7 = $ ss.
• For the second query, $S_4S_5\ldots S_{10} = $ sissipp has two places where the same lowercase English letter occurs twice in a row: $S_6S_7 = $ ss and $S_9S_{10} = $ pp.
• For the third query, $S_4S_5S_6 = $ sis has zero places where the same lowercase English letter occurs twice in a row.
• For the fourth query, $S_7 = $ s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

4

$S_1S_2\ldots S_5 = $ aaaaa has four places where the same lowercase English letter occurs twice in a row: $S_1S_2 = $ aa, $S_2S_3 = $ aa, $S_3S_4 = $ aa, and $S_4S_5 = $ aa.

问题描述

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

此外，你还有关于字符串 $S$ 的 $Q$ 个查询。对于 $i = 1, 2, \ldots, Q$，第 $i$ 个查询由两个整数 $l_i, r_i$ 表示，询问如下。

在字符串 $S$ 的子串 $S_{l_i}S_{l_i+1}\ldots S_{r_i}$（范围从第 $l_i$ 个到第 $r_i$ 个字符），有多少个地方是连续出现相同的小写英文字母的？换句话说，有多少个整数 $p$ 满足 $l_i \leq p \leq r_i-1$ 且 $S_p = S_{p+1}$？

对每个查询打印答案。

约束

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