D 小红的好串

思路：核心就是弄明白如何找出red序列的几种情况

1. 我们可以分为三类情况来讨论。

2. 根据待求序列的长度模3的结果进行分类

   （1）len % 3 == 0 比如len = 6 ： 好串为：rreedd

   （2）len % 3 == 1 比如len = 4 : 好串为：rred reed redd

   （3）len % 3 == 2 比如len = 5 : 好串为：rreed rredd reedd

3. 所以我们根据以上情况，求得每个子串变为对应的类的最小操作次数即可

4. 我们如何求变化到目的串要进行的操作数呢，我们可以用一个前缀和数组来求。

• sum[i][j] ：前i个字符中j字符有几个
• 那么我们把[l,r] 的字串改为字符c的字串的操作次数为：res = r - l + 1 - (sum[r][c] - sum[l-1][c])

5. 当串长度小于2时，一定为好串，因为都只能产生0个red，所以要特判一下

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int sum[N][26];
int solve(int l, int r, char c)
{
    int cnt = sum[r][c - 'a'] - sum[l - 1][c - 'a'];
    int res = r - l + 1 - cnt;
    return res;
}
int main()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    s  = " " + s;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j < 26; j ++)
        {
             sum[i][j] = sum[i-1][j];
        }
        sum[i][s[i] - 'a'] ++;
    }
    
    while (q--)
    {
        int l, r, res = 1e9 + 10;
        cin >> l >> r;
        int len = r - l + 1;
        if(len <= 2) cout << 0 << endl;
        else
        {
            if(len % 3 == 0)
            {
                int t = len / 3;
                res = min(res, solve(l, l + t - 1, 'r') + solve(l + t, l + t * 2 - 1, 'e') + solve(l + t * 2, l + t * 3 - 1, 'd'));
            }
            else if(len % 3 == 1)
            {
                int t = len / 3;
                res = min(res, solve(l, l + t, 'r') + solve(l + t + 1, l + t * 2, 'e') + solve(l + t * 2 + 1,l +  t * 3, 'd'));
                res = min(res, solve(l, l + t - 1, 'r') + solve(l + t, l + t * 2, 'e') + solve(l + t * 2 + 1, l + t * 3, 'd'));
                res = min(res, solve(l, l + t - 1, 'r') + solve(l + t, l + t * 2 - 1, 'e') + solve(l + t * 2, l + t * 3, 'd'));
            }
            else if(len % 3 == 2)
            {
                int t = len / 3 + 1;
                res = min(res, solve(l, l + t - 1, 'r') + solve(l + t, l + t * 2 - 1, 'e') + solve(l + t * 2, l + t * 3 - 2, 'd'));
                res = min(res, solve(l, l + t - 1, 'r') + solve(l + t, l + t * 2 - 2, 'e') + solve(l + t * 2 - 1, l + t * 3 - 2, 'd'));
                res = min(res, solve(l, l + t - 2, 'r') + solve(l + t - 1, l + t * 2 - 2, 'e') + solve(l + t * 2 - 1, l + t * 3 - 2, 'd'));
            }
            cout << res << endl;
        }
    }

    return 0;
}