Consecutive

题目描述

给定长度为 $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}$？

对于每个 $Q$ 个查询，输出答案。

输入格式

输入按照标准输入给出，格式如下： $N$ $Q$ $S$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_Q$ $r_Q$

输出格式

输出 $Q$ 行。 对于 $i = 1, 2, \ldots, Q$，第 $i$ 行应当包含第 $i$ 个查询的答案。

11 4
mississippi
3 9
4 10
4 6
7 7

2
2
0
0

5 1
aaaaa
1 5

4

提示

$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$对四个查询的答案如下。

对于第一个查询，$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$ 有零个位置存在相同的小写英文字母连续出现两次。
$S_1S_2\ldots S_5 =$ $aaaaa$ 有四个位置存在相同的小写英文字母连续出现两次： $S_1S_2 =$ $aa$, $S_2S_3 =$ $aa$, $S_3S_4 =$ $aa$, 和 $S_4S_5 =$ $aa$.

标签: AtCoder|abc328C

来源

AtCoder|abc328C