[数据结构与算法]D.Say No to Palindromes（前缀和

D. Say No to Palindromes
题意：
定义一个字符串是好串，当且仅当 $s$ 不包含任何长度大于等于 $2$ 的回文子串。
给定一个长度为 $n$ 的字符串（仅包含 $a,b,c$ 三种字符）和 $m$ 个询问，每次询问查询一个区间 $[l,r]$，求将字符串 $S_{l...r}$ 变成好串至少需要修改多少字符。
思路：
因为字符串的组成仅有 $3$ 种字符
模拟一下好串的特征，初始为 $a$，添加一个 $b$，下一个只能添加 $c$，否则 $aba$ 或者 $abb$ 都不是好串，再往后加只能加 $a$，就进入循环了，也就是好串仅有 $abc$ 这样的子串循环构成，$abcabca$
$abc$ 这样的子串有 $A_3^3$ 种
维护一个由第 $j$ 种子串构成字符串时，需要修改的字符个数的前缀和
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
string s;
char t[6][5] = {"abc", "acb", "bac", "bca", "cab", "cba"};
int f[maxn][6];

void work()
{
	cin >> n >> m;
	cin >> s; s = "@" + s;
	for(int i = 1; i <= n; ++i){
		int k = (i - 1) % 3;
		for(int j = 0; j < 6; ++j)
			f[i][j] = f[i-1][j] + (s[i] != t[j][k]);
	}
	while(m--){
		int l, r;cin >> l >> r;
		int ans = inf;
		for(int i = 0; i < 6; ++i) ans = min(ans, f[r][i] - f[l-1][i]);
		cout << ans << endl;
	}	
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}