D. Say No to Palindromes

题目描述：

给你一个只有abc三种字符的字符串，m次询问，每次询问都是问最少需要进行多少次操作才能使得区间[l, r]中没有长度大于等于2的子串是回文串，每次操作都是是选择一个字符，将其改成abc中的另一个字符

思路：

要想一个串没有任何子串是回文串，需要满足的条件是以一个顺序一直循环下去，比如abcabcabc、cabcabcab等等，其他情况都不可以，也就是s[i] = s[i + 3] = s[i + 6]……, s[i + 1] = s[i + 4] = s[i + 7]……, s[i + 2] = s[i + 5] = s[i + 8]……

循环的顺序只有6种，{abc, acb, bac, bca, cab, cba}，所以开个二维数组，对每种情况都去跑一遍进行匹配，看看每个字符到底需不需要加1，对每种循环顺序的数组都求一次前缀和就行，查询的时候求$min(pre[i] [r] - pre[i] [l - 1])，1<=i<=6$即可

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sz(x) (int)(x).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k;
int x, y, z;
int l, r;
int pre[10][MAX];
char tr[MAX];
char p[10] = {'a', 'a', 'b', 'c'};
void work(){
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        cin>>tr[i];
    }
    for(int i = 1; i <= 6; ++i){
        for(int j = 1; j <= n; ++j){
            pre[i][j] = pre[i][j - 1] + (tr[j] != p[(j - 1)% 3 + 1]);
        }
        next_permutation(p + 1, p + 4);
    }
    while (m--) {
        cin>>l>>r;
        int minx = inf;
        for(int i = 1; i <= 6; ++i){
            minx = min(minx, pre[i][r] - pre[i][l - 1]);
        }
        cout<<minx<<endl;
    }
}

int main(){
    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}