GeT AC [AtCoder Beginner Contest 122 C]

https://atcoder.jp/contests/abc122/tasks/abc122_c

前提知識

• https://www.hamayanhamayan.com/entry/2017/07/04/020117:titl=累積和

解説

https://atcoder.jp/contests/abc122/submissions/4712429

最初の考察が一番むずかしいと思うが、本題よりもう少し簡単なAが何個あるかを考えてみよう。
すると、以下の解法にたどり着きやすいかもしれない。
　
ok[i] := S[i]とS[i+1]でACとなるなら1, そうでないなら0
これをまずは作ろう。
すると、クエリの答えは
ok[L] + ok[L+1] + ... ok[R - 1]
となる。
和でok[R]が無いのは、S[R+1]が範囲に含まれないからである。
　
ここまでくれば後は、アルゴリズムを適用するだけである。
累積和というアルゴリズムを使えば、区間和がO(1)で得られるので、各クエリO(1)で解ける。
全体O(Q)でAC。

int N, Q; string S;
int ok[101010], sm[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> Q >> S;
	rep(i, 0, N - 1) if (S[i] == 'A' and S[i + 1] == 'C') ok[i] = 1;
	sm[0] = ok[0];
	rep(i, 1, N) sm[i] = sm[i - 1] + ok[i];
 
	rep(q, 0, Q) {
		int L, R; cin >> L >> R; L--; R--;
 
		int ans = sm[R-1];
		if (L) ans -= sm[L - 1];
		
		printf("%d\n", ans);
	}
}