分数: 300 点
问题陈述
给你一个字符串 S 长度 N 组成 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 是从开头和结尾删除零个或多个字符得到的字符串 T.
例如,子字符串 ATCODER 包括 TCO, AT, CODER, ATCODER 和 (空字符串),但不是 AC.
约束
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- S 是一个长度为 N.
- 中的每个字符 S is
A,C,GorT. - 1 \leq l_i < r_i \leq N
输入
输入由标准输入按以下格式给出:
N Q S l_1 r_1 : l_Q r_Q
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i- 第一个查询。
示例输入 1
8 3 ACACTACG 3 7 2 3 1 8
示例输出 1
2 0 3
- 查询 1: 的子串 S 从索引处开始 3 并以索引结束 7 is
ACTAC。在这个字符串中,AC作为子字符串出现两次。 - 查询 2: 的子串 S 从索引处开始 2 并以索引结束 3 is
CA。在这个字符串中,AC作为子字符串出现零次。 - 查询 3: 的子串 S 从索引处开始 1 并以索引结束 8 is
ACACTACG。在这个字符串中,AC作为子字符串出现 3 次。