A5392. AA的C
编程题
普及/提高-
知识点
题目描述
给定一个只由
接下来有 $Q$ 次询问。每次给出区间 $[l,r]$（$1\le l<r\le N$），请你只在 $S$ 的子串 $S[l..r]$ 中统计
形式化地说，就是统计满足 $l\le i<r$ 且 $S[i]=\texttt{'A'}$ 且 $S[i+1]=\texttt{'C'}$ 的下标 $i$ 的个数。
A/C/G/T 构成的字符串 $S$（长度为 $N$）。我们把形如相邻两字符为 A 接着 C 的位置视作一次出现（也就是统计相邻子串 AC 的出现次数，可相互不重叠、但天然不会重叠，因为都是相邻两位）。接下来有 $Q$ 次询问。每次给出区间 $[l,r]$（$1\le l<r\le N$），请你只在 $S$ 的子串 $S[l..r]$ 中统计
AC 出现了多少次。形式化地说，就是统计满足 $l\le i<r$ 且 $S[i]=\texttt{'A'}$ 且 $S[i+1]=\texttt{'C'}$ 的下标 $i$ 的个数。
输入格式
第一行：两个整数 $N, Q$。
第二行：一个长度为 $N$ 的字符串 $S$，仅包含字符
随后 $Q$ 行：每行两个整数 $l, r$（$1\le l<r\le N$）。
第二行：一个长度为 $N$ 的字符串 $S$，仅包含字符
A, C, G, T。随后 $Q$ 行：每行两个整数 $l, r$（$1\le l<r\le N$）。
输出格式
输出共 $Q$ 行，每行一个整数，表示对应区间中 "AC" 的出现次数。
输入输出样例
输入 #1
7 3 ACACAGT 1 7 2 5 3 4
输出 #1
2 1 1
说明/提示
$1 \le N \le 10^5$
$1 \le Q \le 10^5$
$S$ 仅由
$1 \le l < r \le N$
对于样例：
区间 $[1,7]$: ACACAGT 中 "AC" 出现在位置 $1$ 和 $3$，共 $2$ 次。
区间 $[2,5]$: 子串 CACA 中只有一次 "AC"（在子串的第 2、3 位）。
区间 $[3,4]$: 子串正好是 AC，出现 $1$ 次。
$1 \le Q \le 10^5$
$S$ 仅由
A/C/G/T 组成$1 \le l < r \le N$
对于样例：
区间 $[1,7]$: ACACAGT 中 "AC" 出现在位置 $1$ 和 $3$，共 $2$ 次。
区间 $[2,5]$: 子串 CACA 中只有一次 "AC"（在子串的第 2、3 位）。
区间 $[3,4]$: 子串正好是 AC，出现 $1$ 次。