TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5837
  • Problem
  • P5837基因中有AC
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,512m
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    8 3
    ACACTACG
    3 7
    2 3
    1 8

    Sample Output

    2
    0
    3

    Hint

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


    Source  ABC122C