C - Consecutive Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

英小文字のみからなる長さ N の文字列 S = S_1S_2\ldots S_N が与えられます。

また、S に関する Q 個の質問が与えられます。 i = 1, 2, \ldots, Q について、i 番目の質問は 2 つの整数 l_i, r_i で表される下記の質問です。

S の l_i 文字目から r_i 文字目までからなる部分文字列 S_{l_i}S_{l_i+1}\ldots S_{r_i} において、 同じ英小文字が 2 つ隣りあう箇所は何個ありますか？ すなわち、l_i \leq p \leq r_i-1 かつ S_p = S_{p+1}を満たす整数 p は何個ありますか？

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

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

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 の 4 個です。

Score : 300 points

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.