AtCoder Beginner Contest 122：C - GeT AC
問題
解法
N, Q <= 10^5 より，各クエリごとに文字列を走査していては間に合わない．そこで，各クエリに O(1) で答えられるようにする．
imos_i := i 文字目までに登場する "AC" の数
とおくと，各クエリで求める値は imos_r - imos_l となる．ここで imos_(l - 1) ではなく imos_l となるのは，"AC" の数が増えるのは 'C' の箇所であり，前者で処理をすることにすると，クエリで指定された区間が "C..." と C で始まっている場合，正しい答えより 1 大きくなってしまう．そこで，imos_l を引くことで "AC..." とクエリの区間がなっていた場合でも答えに影響なく正しい答えを求めることは出来る．O(N + Q)．
解答
