ABC122 C問題 GeT AC を累積和で解く

累積和のアルゴリズムの勉強のためにABC122 C問題を解いて、解説します。

atcoder.jp

A, C, G, Tという文字からなる文字列が与えられた時に、指定された区間でACは何回あらわれるか求める問題です。

文字列の長さNは 2 \leq N \leq 10^5、指定される区間(クエリ)の個数Qは 1 \leq Q \leq 10^5
単純にクエリごとにN文字を捜索していては、 10^{10}になってしまうので、工夫が必要です。

累積和の考え方でいくと、事前に区間ごとにACの累積出現回数を計算することを考えます。
そして、区間a文字目〜b文字目の間の出現回数を求められたら、「最初からb文字目までの出現回数」から「最初からa文字目までの出現回数」を引いて求めます。

問題のサンプルでは、"ACACTACG"という文字列が与えられて、3文字目から7文字目でACが出現する回数を聞かれています。
配列のインデックスは0から始まるので、累積和の配列をaccとすると、acc[6] - acc[2] = 3 - 1 = 2 という風に計算できるように累積和を記録する配列を作ります。

N, Q = map(int, input().split())
S = input()
acc = [0 for _ in range(N + 1)]
for i in range(1, N):
    if S[i - 1] == 'A' and S[i] == 'C':
        acc[i] = acc[i - 1] + 1
        continue
    acc[i] = acc[i - 1]

for _ in range(Q):
    l, r = map(int, input().split())
    print(acc[r - 1] - acc[l - 1])

典型的な累積和の問題でした。