Say No to Palindromes（暴力/前缀和）

题目 题意：给定长度为n的字符串，字符串只包含a,b,c三种字符。m次查询，每次查询区间[l,r]中最少需要修改多少个字符（只能改成a,b,c三种字符），把该字符串变成beautiful。一个字符串是beautiful的定义：它的任何长度大于1的字符子串都是非回文。 题解：考虑一个字符串怎么样才能是beautiful的。 1、因为长度为2的子串不能是回文串，所以相邻的字符不能相同； 2、因为长度为3的子串不能是回文串，所以间隔为1的字符不能相同。 此外，如果一个字符串不存在长度为2和为3的回文串，那么显然它不存在长度大于3的回文串了，因此，我们只要满足1和2就可以保证字符串是beautiful的。 而为了保证1和2，我们发现字符串的每3个字符都一定要互不相同。因此，一个beautiful的字符串一定循环的，且循环节有6种情况： a b c , a c b , b a c , b c a , c a b , c b a abc, {acb},bac,bca,cab,cba abc,acb,bac,bca,cab,cba。

现在，因为有多次查询，我们可以用前缀和，预处理计算每个下标，每个字符的累计出现次数。详见代码。

#include 
using namespace std;
const int maxn = 200010;

int n, m;
char s[maxn];
// pre[i][pos][idx]表示前i个字符中下标位置模3为pos，字符为idx + 'a'的总数 
int pre[maxn][3][3];
 

void init() {
	memset(pre, 0, sizeof(pre));

	for (int i = 1; i