AT_abc122_c [ABC122C] GeT AC
题目描述
给定一个长度为 n 的、仅由 ‘A’、‘C’、‘G’、‘T’ 构成的字符串 s。请回答以下 q 个问题:
∙问题 i(1≦i≦q):给定整数 li,ri(1≦li<ri≦n),考虑 s 的第 li 个字符到第 ri 个字符(包括两端)组成的子串,问在这个子串中,"AC" 作为子串出现了多少次。
【名词解释】
∙ 子串:子串为从原字符串中连续选择一段字符(可以全选、可以一个字符也不选)得到的新字符串。例如,"ATCODER" 的子串包括 "TCO"、"AT"、"CODER"、"ATCODER" 和空串,但不包括 "AC"。
输入格式
第一行输入两个整数 $n,q \left(2 \leqq n \leqq 10^5;\ 1 \leqq q \leqq 10^5\right)$ 分别代表字符串长度和问题数量。
第二行输入一个长度为 n 的、仅由字符 ‘A’、‘C’、‘G’、‘T’ 构成的字符串 s。
此后 q 行,第 i 行输入两个整数 li,ri(1≦li<ri≦n) 代表第 i 个问题涉及的区间。
输出格式
输出 q 行,第 i 行输出一个整数,代表第 i 个问题的答案。
测试样例
8 3
ACACTACG
3 7
2 3
1 8
2
0
3
样例 1 解释
三个问题依次为:
∙问题 1:s 的第 3 个字符到第 7 个字符组成的子串为 "ACTAC",其中 "AC" 作为子串出现了 2 次;
∙问题 2:s 的第 2 个字符到第 3 个字符组成的子串为 "CA",其中 "AC" 作为子串出现了 0 次;
∙问题 3:s 的第 1 个字符到第 8 个字符组成的子串为 "ACACTACG",其中 "AC" 作为子串出现了 3 次。