TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5837
  • 题目
  • P5837基因中有AC
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512m
    问题描述

    人类基因由碱基'A','C','G','T'构成。
    何老板检查了一下自己的DNA,拿到了检查报告。
    检测报告里有一段长度为N的由字母'A','C','G','T'构成的表示基因片段的字符串。
    何老板发现,自己的基因中带了很多“AC”,众所周知他的口号是“Life is short,AC more!”,于是他想知道对于该基因片段中的任意一段区间[L,R]中,出现了多少次“AC”,请你快速帮他做出回答。

    输入格式

    第一行,两个整数N和Q,N表示基因长度,Q表示询问次数
    第二行,一个长度为N的字符串,表示基因片段
    接下来Q行,每行两个整数L,R,表示一次询问

    输出格式

    Q行,每行一个整数依次表示每次询问的答案

    样例输入

    8 3
    ACACTACG
    3 7
    2 3
    1 8

    样例输出

    2
    0
    3

    提示

    \(1≤N≤2*10^5\)
    \(1≤Q≤10^5\)
    \(1≤L≤R≤N\)


    来源  ABC122C