Educational Codeforces Round 112 D. Say No to Palindromes

题目链接：D. Say No to Palindromes
题意：定义一个字符串是美丽的，当且仅当字符的任意长度大于$1$的子串不是回文串。给定仅由三个小写字母$a,b,c$组成的长度为$n$的字符串，你能将字符串的任意字母更改为$a,b,c$三个小写字母的任意一个，更改一个字母的花费为$1$。 询问$m$次，每次询问$[l,r]$区间的子串的变成美丽的串的最小花费。

思路： 因为字母仅有$a,b,c$三个小写字母，可以自己在纸上写几个子串，观察怎样构造才是美丽的字符串。然后可以得到，1. 长度为$1$的子串是美丽的。2. 长度为$2$的子串，两个字符不同即可。3. 当长度等于$3$时，我们将$a,b,c$任意排列即可，而长度大于$3$的串 只需要按顺序与前三个字符相同即可，即构造长度为$7$的字符串，若前三个是$"abc"$则$str="abcabca"$,若前三个是 $"bac"$则$str="bacbacb"$。而$abc$三个字母的所有排列只有6种

{
    "abc","acb","bac","bca","cab","cba"};

现在知道完美的串的构造方法，再看问题，$m$次提问$m<=2e5,l<=r<=n$。我们尝试用暴力的方法，每次自己设定前三个字母 ，按顺序去排列，若与原字符串不符合花费+1,因为前三个的排列方式有6种，只需要枚举6次取最大值即可。但考虑到数据范围，每次对区间遍历的时间复杂度为$O(n)$ 而有$m$次询问，总体复杂度为$O(n\ast m)$显然是我们不能接受的，那么有什么加快的方式吗？
我们想到区间询问可以用前缀和来$O(1)$查询。于是我们枚举6种开头的排列方式对整个字符串进行花费的求解 （枚举整个字符串的开头，对于我们询问的区间的开头6种方案也包括在内，同样可以在纸上略微构造可得），并以前缀和的方式记录，最后的时间复杂度 预处理：$O(6n)$ + 查询$O(1m)$总复杂度：$O(n+m)$。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n,m;
char a[N];
char p[6][4] = {
    "abc","acb","bac","bca","cab","cba"};//枚举6种方式
int sum[6][N];//前缀和

int main()
{
    
    scanf("%d%d%s",&n,&m,a + 1);
    for(int i=0;i<6;i++){
    //预处理
        for(int j=1;j<=n;j++)
        {
    
            if(a[j] != p[i][j % 3])sum[i][j] = 1;//虽然字符串以1开头方便前缀和计算，但也不影响取模排列,abc->bca整体右移一位
            sum[i][j] += sum[i][j - 1];
        }
    }
    while(m --)
    {
    
        int l,r;
        scanf("%d%d",&l,&r);
        int ans = r - l + 1;
        for(int i=0;i<6;i++){
    
            ans = min(ans , sum[i][r] - sum[i][l - 1]);
        }
        printf("%d\n",ans);
    }
    return 0;
}