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
.