TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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