AtCoder-Contest122-C题-GetAC之前缀和预处理

C题传送门

题目的意思大概就是给你一个长度为N的字符串，M次询问区间，问你L，R中有多少个AC子列

这种题很明显是要预处理的，简单的一维前缀和处理，否则肯定超时

前缀处理只需要O(n+m)

开一个数组，下标 i 表示到第 i 个位置有多少个AC

所有答案所求的区间就可以之间相减结果 ，而不用循环去找

题面如下：

样例:

输入
8 3
ACACTACG
3 7
2 3
1 8

输出：
2
0
3

我的AC代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    int n , m;
    cin>>n>>m;
    getchar();
    string str;
    getline( cin , str );
    
    int cnt[n];
    fill( cnt , cnt + n , 0 );
    for( int i = 1 ; i < str.length() ; i++ ){
    	if( str[i] == 'C' ){
    		if( str[i - 1] == 'A' ){
    			cnt[i] += cnt[i - 1] + 1;
			}
			else{
				cnt[i] += cnt[i - 1];
			}
		}
		else cnt[i] += cnt[i - 1];
	}
	
//	for( int i = 0 ; i < n ; i++ ){
//		cout<<cnt[i]<<" ";
//		if( i == n - 1 ) cout<<'\n';
//	}
    for( int i = 0 ; i < m ; i++ ){
    	int l , r;
    	cin>>l>>r;
    	cout<<cnt[r - 1] - cnt[l - 1]<<'\n';
	}
    
    return 0;
}