C - GeT AC

得分：$300$ 分

问题描述

给定一个长度为 $N$ 的字符串 $S$，由字符 A，C，G 和 T 组成。回答以下 $Q$ 个查询：

• 查询 $i$ ($1 \leq i \leq Q$)：给出整数 $l_i$ 和 $r_i$ ($1 \leq l_i < r_i \leq N$)。考虑字符串 $S$ 中从索引 $l_i$ 到索引 $r_i$ (两者都包含) 的子串。在这个子串中，有多少次子字符串 AC 出现？

注意事项

字符串 $T$ 的子串是通过从开头和末尾移除零个或多个字符获得的字符串。

例如，字符串 ATCODER 的子串包括 TCO，AT，CODER，ATCODER 和 (空字符串)，但不包括 AC。

约束条件

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $S$ 的长度为 $N$。
• $S$ 中的每个字符是 A，C，G 或 T。
• $1 \leq l_i < r_i \leq N$

输入

从标准输入中按以下格式输入：

$N$ $Q$

$S$

$l_1$ $r_1$

:

$l_Q$ $r_Q$

输出

输出应包含 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

8 3
ACACTACG
3 7
2 3
1 8

2
0
3

• 查询 $1$：字符串 $S$ 中从索引 $3$ 到索引 $7$ 的子串是 ACTAC。在这个子串中，AC 作为子字符串出现了两次。
• 查询 $2$：字符串 $S$ 中从索引 $2$ 到索引 $3$ 的子串是 CA。在这个子串中，AC 作为子字符串出现了零次。
• 查询 $3$：字符串 $S$ 中从索引 $1$ 到索引 $8$ 的子串是 ACACTACG。在这个子串中，AC 作为子字符串出现了三次。