← 返回题目列表

AtCoder · abc122_c

C. 拿到AC

中文机器翻译题面 查看原题

分数: 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, G or T.
  • 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 次。