1555D - Say No to Palindromes - CodeForces Solution

#include<bits/stdc++.h>
#include<math.h>
#include<unordered_set>
#include <unordered_map>
#define ll long long int
#define pb push_back
#define mp make_pair
#define edge(x,y,v) v[x].pb(y);v[y].pb(x); 
#define fori(i,n) for(ll i=0;i<n;i++)
#define fori1(i,n) for(ll i=1;i<=n;i++)
#define all(v) v.begin(),v.end()
#define disp(v) for(ll vid = 0;vid<v.size();vid++)cout<<v[vid]<<" ";
#define vll vector<ll>
#define mapl map<ll,ll>
#define input freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define Nitro ios_base::sync_with_stdio(false); cin.tie(NULL);
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define pll pair<ll,ll>
using namespace std; 
const ll M=1e9+7;
 
/*
long long primf(long long x, long long n, long long k) {
    x %= k;
    long long res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * x % k;
        x = x * x % k;
        n >>= 1;
    }
    return res;
}
*/
/*
ll primf(ll x, ll n, ll m){
    ll res = 1%m;
    while(n--){
        res*=x;
        res = res%m;
    }
    return res;
}


ll geom(ll r, ll n, ll m){
    if(n==2) return (primf(r,0,m) + primf(r,1,m) + primf(r,2,m))%m;
    else if(n==1) return (primf(r,0,m) + primf(r,1,m))%m;
    else if(n==0) return 1%m; 
    else if(n%2==0) return (((primf(r,n/2+1,m) + 1%m)* geom(r,n/2-1,m))%m + primf(r,n/2,m))%m;
    else{
        return (geom(r,n/2,m) * (primf(r,n/2+1,m) + 1%m))%m;
    }
}
*/
/*
ll binpow(ll a, ll b) {
    if (b == 0)
        return 1;
    ll res = binpow(a, b / 2)%M;
    if (b % 2)
        return ((res%M * res%M)%M * a%M)%M;
    else
        return (res%M * res%M)%M;
}
*/
/*
const ll N=200006;
ll parent[N];
ll sizes[N];
void make(ll v){
    parent[v]=v;
    sizes[v]=1;
}
 
int find(ll v){
    if(parent[v]==v) return v;
    return parent[v]=find(parent[v]);
}
 
void Union(ll a, ll b){
    a = find(a);
    b = find(b);
    if(a!=b){
        if(sizes[a]>sizes[b]) swap(a,b);
        parent[a]=b;
        sizes[b]=sizes[a]+sizes[b];
    }
}
*/

/*
ll find_bits(ll n){
    ll cnt=1;
    while(n>>=1){
        cnt++;
    }
    return cnt;
}
*/

/*
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
*/
const ll N = 2e5+5;
vector<ll> arr[N];
string s;
ll func(string ss, ll i){
    if(ss[i%3]==s[i]) return 1;
    return 0;
}
void FuckMyBrain(){
    ll n,m;
    cin>>n>>m;
    cin>>s;
    ll cnt,f;
    fori(i,6) arr[0].pb(0);
    fori(i,n){
        if(func("abc",i)) arr[i+1].pb(arr[i][0]+1);
        else arr[i+1].pb(arr[i][0]);
        if(func("acb",i)) arr[i+1].pb(arr[i][1]+1);
        else arr[i+1].pb(arr[i][1]);
        if(func("bac",i)) arr[i+1].pb(arr[i][2]+1);
        else arr[i+1].pb(arr[i][2]);
        if(func("bca",i)) arr[i+1].pb(arr[i][3]+1);
        else arr[i+1].pb(arr[i][3]);
        if(func("cab",i)) arr[i+1].pb(arr[i][4]+1);
        else arr[i+1].pb(arr[i][4]);
        if(func("cba",i)) arr[i+1].pb(arr[i][5]+1);
        else arr[i+1].pb(arr[i][5]);
    }
    fori(i,m){
        ll x,y;
        cin>>x>>y;
        ll num=0;
        fori(j,6){
            num = max(num,arr[y][j]-arr[x-1][j]);
        }
        cout<<(y-x+1)-num<<endl;
    }
}


int main(){
    //input;
    Nitro;
//XXXXXXXXXXXXXXXXXXXXXXXXXX
    ll repeat_mf;
    repeat_mf=1;
    //cin>>repeat_mf; //COMMENT OUT
    while(repeat_mf--){
        FuckMyBrain();
    }
return 0;
}