题解

前缀和优化.

我们用dp[i]表示到下标i时出现的AC次数

• 如果遇到AC组合，dp[i]=++cnt（cnt代表AC出现次数）
• 否则dp[i]=dp[i-1]（没出现顺承上个状态）
  注意字符串下表从0开始
  参考代码：

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n,q;cin>>n>>q;
    string s;cin>>s;
    int dp[100005],cnt=1;
    dp[0]=0;
    for(int i=1;i<n;i++){
        if(s[i-1]=='A'&&s[i]=='C') dp[i]=cnt++;
        else dp[i]=dp[i-1];
    }
    while(q--){
        int l,r;cin>>l>>r;
        cout<<dp[r-1]-dp[l-1]<<endl;
    }
    return 0;
}