题目链接。

解析

考虑最终序列。由于序列较长，先考虑序列短小的情况，即长度为 $3$ 时。

对于一个长度为 $3$ 的序列 $S_{1,2,3}$，要使其不存在回文串，需要满足 $S_1\neq S_2,S_2\neq S_3,S_1\neq S_3$，你发现这三个字母必须是互不相同的，由于字符串仅由三种字母组成，最终序列的前三个字母一定是以下六种情况的一种并由其中一种情况循环得到：abc,acb,bac,bca,cab,cba。

问题转化为了给定一个区间，将这个区间改变为以上六种循环中的一种的最小操作次数。而对于某种循环的操作次数即为当前序列与最终序列不同的字符个数，这可以使用前缀和来维护。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m;
char a[N],s[7][3]={{'a','b','c'},{'a','c','b'},{'b','a','c'},{'b','c','a'},{'c','a','b'},{'c','b','a'}};
int sum[N][7];
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s",a+1);
    for(int k=0;k<=6;k++){
        int now=0;
        for(int i=1;i<=n;i++,now++){
            if(now==3) now=0;
            if(a[i]!=s[k][now]) sum[i][k]++;
            sum[i][k]+=sum[i-1][k];
        }//六种情况的前缀和
    }
    for(int i=1,l,r;i<=m;i++){
        scanf("%d%d",&l,&r);
        int ans=1e9;
        for(int k=0;k<=6;k++){
            ans=min(ans,sum[r][k]-sum[l-1][k]);
        }//选取代价最小的那一个
        printf("%d\n",ans);
    }
    return 0;
}