AtCoder Beginner Contest 122 C問題

AtCoder Beginner Contest 122 - AtCoder

C問題

素直に全探索したらO(N^2)になってしまい間に合わないので、累積和を用いて解いてみた。
もっとうまく書けるんだろうけど、まあ始めのうちは泥臭いやり方でもいいでしょ!いいはず!

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  S += 'X'; // この後のfor探索でSの文字数+1まで参照してしまうため、最後に1文字追加

// 累積和を利用して 0112222333344455 のようにAC数を保存する配列を作る
  vector<int> vec(N + 1); 
  vec.at(0) = 0;
  int ACcount = 0; 
  for (int i = 1; i <= N; i++){
    if (S.at(i-1) == 'A' && S.at(i) == 'C'){
      ACcount++;
      vec.at(i) = ACcount;
    } else {
      vec.at(i) = ACcount;
    } 
  }   

// r番目の値からl番目の値を引き算すれば範囲内のAC数が分かるはず
  for (int i = 0; i < Q; i++){
    int l,r;
    int count = 0;
    cin >> l >> r;
    count = vec.at(r - 1) - vec.at(l - 1); 
    cout << count << endl;   
  } 
}