#ABC122C. 多少个AC?

多少个AC?

AT_abc122_c [ABC122C] GeT AC

题目描述

\hspace{15pt}给定一个长度为 nn 的、仅由 ‘A’\texttt{`A'}、‘C’\texttt{`C'}、‘G’\texttt{`G'}、‘T’\texttt{`T'} 构成的字符串 ss。请回答以下 qq 个问题:

∙ \hspace{23pt}\bullet\,问题 i(1≦i≦q)i \left(1 \leqq i \leqq q\right):给定整数 li,ri(1≦li<ri≦n)l_i,r_i \left(1 \leqq l_i < r_i \leqq n\right),考虑 ss 的第 lil_i 个字符到第 rir_i 个字符(包括两端)组成的子串,问在这个子串中,"AC"\texttt{"AC"} 作为子串出现了多少次。

\hspace{15pt}【名词解释】

∙ \hspace{23pt}\bullet\, 子串:子串为从原字符串中连续选择一段字符(可以全选、可以一个字符也不选)得到的新字符串。例如,"ATCODER"\texttt{"ATCODER"} 的子串包括 "TCO"\texttt{"TCO"}、"AT"\texttt{"AT"}、"CODER"\texttt{"CODER"}、"ATCODER"\texttt{"ATCODER"} 和空串,但不包括 "AC"\texttt{"AC"}。

输入格式

\hspace{15pt}第一行输入两个整数 $n,q \left(2 \leqq n \leqq 10^5;\ 1 \leqq q \leqq 10^5\right)$ 分别代表字符串长度和问题数量。

\hspace{15pt}第二行输入一个长度为 nn 的、仅由字符 ‘A’\texttt{`A'}、‘C’\texttt{`C'}、‘G’\texttt{`G'}、‘T’\texttt{`T'} 构成的字符串 ss。

\hspace{15pt}此后 qq 行,第 ii 行输入两个整数 li,ri(1≦li<ri≦n)l_i,r_i \left(1 \leqq l_i < r_i \leqq n\right) 代表第 ii 个问题涉及的区间。

输出格式

\hspace{15pt}输出 qq 行,第 ii 行输出一个整数,代表第 ii 个问题的答案。

测试样例

8 3
ACACTACG
3 7
2 3
1 8
2
0
3

样例 1 解释

\hspace{15pt}三个问题依次为:

∙ \hspace{23pt}\bullet\,问题 11:ss 的第 33 个字符到第 77 个字符组成的子串为 "ACTAC"\texttt{"ACTAC"},其中 "AC"\texttt{"AC"} 作为子串出现了 22 次;

∙ \hspace{23pt}\bullet\,问题 22:ss 的第 22 个字符到第 33 个字符组成的子串为 "CA"\texttt{"CA"},其中 "AC"\texttt{"AC"} 作为子串出现了 00 次;

∙ \hspace{23pt}\bullet\,问题 33:ss 的第 11 个字符到第 88 个字符组成的子串为 "ACACTACG"\texttt{"ACACTACG"},其中 "AC"\texttt{"AC"} 作为子串出现了 33 次。