笨蛋也能看懂（就是啰嗦）

知识点：线段树 树状数组

我们来一步步推出做法。

1、首先思考 ，即长度大于等于2的回文串。

2、为了不出现如 或 这样的回文串，我们要保证连续三个字符都不一样。

3、即整个字符串 都是按照一个顺序重复排列的，例如 “” 或 “” 。而 的不同排序一共有 种：、、、、、。

4、那么对于操作 询问区间 ~ 的子串是否是字串，我们只要看该子串需要修改几个字符就可以形成上述排序的重复排列。

例如：

s = r e d e d r e r r

变为

r e d r e d r e d

需要修改 个字符。但要变为

e d r e d r e d r 

只需要修改 个字符。对于全部 种排序，我们都枚举一遍后取最小值就行。

但是这样做，每次操作 的时间复杂度是 ，太慢了。

我们想办法优化。

比如计算字符串 成为 的重复排列需要修改几个字符，就是遍历 的所有字符逐步对比，如果 与预想的字符有出入，我们把它记作要修改的字符，计数器 + ，最后查看 的值即可知道修改次数了。

这一过程，其实就是计算子串 ，而想要快速得到区间和，我们可以采用前缀和的方法。

若不考虑操作 这题就变成了： 。

预处理 转变为 个不同排序的重复排列各需要修改的位置，再处理出前缀和数组。例：

把 s = r e d e d r e r r ,修改为 e d r e d r e d r 。
每个位置的修改次数：1 1 1 0 0 0 0 1 0
前 缀 和 数 组 sum：1 2 3 3 3 3 3 4 4

只需要用 就可以知道把第 到第 个字符的子串需要多少次操作才能变为好串（当然，要对比完全部六种字符排序）。

那么对于操作 ，我们只需要 的复杂度就可以得出结果。这样就可以通过那只有操作 的 的数据了。

引入了操作 后，其实也就是一个对数组进行 和 的线段树裸题。

对于 种不同排序，我们开 个线段树依次处理即可。

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma gcc optimize(2)
//#pragma gcc optimize(3)

#define endl '\n'
#define int ll
#define pi acos(-1)
#define inf 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7, base = 13331;

int n, m, a[N], f[7][N];
int p[7][3] = { {0,0,0}, {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1} };
unordered_map<char, int>mymap;

void build(int idx, int k, int l, int r)
{
    if (l == r)
    {
        f[idx][k] = (p[idx][l % 3] != a[l] ? 1 : 0);
        return;
    }
    int mid = (l + r) / 2;
    build(idx, k + k, l, mid);
    build(idx, k + k + 1, mid + 1, r);
    f[idx][k] = f[idx][k + k] + f[idx][k + k + 1];
}

void revise(int idx, int k, int l, int r, int x)
{
    if (l == r)
    {
        f[idx][k] = (p[idx][l % 3] != a[l] ? 1 : 0);
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)revise(idx, k + k, l, mid, x);
    else revise(idx, k + k + 1, mid + 1, r, x);
    f[idx][k] = f[idx][k + k] + f[idx][k + k + 1];
}

int query(int idx, int k, int l, int r,int x,int y)
{
    if (l == x && r == y)
    {
        return f[idx][k];
    }
    int mid = (l + r) / 2;
    if (y <= mid)return query(idx, k + k, l, mid, x, y);
    else if (x > mid)return query(idx, k + k + 1, mid + 1, r, x, y);
    else
        return query(idx, k + k, l, mid, x, mid) + query(idx, k + k + 1, mid + 1, r, mid + 1, y);
}

void solve()
{
    string s;
    cin >> n >> m >> s;
    mymap['r'] = 1;
    mymap['e'] = 2;
    mymap['d'] = 3;
    for (int i = 1; i <= n; i++)
    {
        a[i] = mymap[s[i - 1]];
    }
    for (int i = 1; i <= 6; i++)
    {
        build(i, 1, 1, n);
    }

    while (m--)
    {
        int st;
        cin >> st;
        if (st == 1)
        {
            int x;
            char c;
            cin >> x >> c;
            a[x] = mymap[c];
            for (int i = 1; i <= 6; i++)revise(i, 1, 1, n, x);
        }
        else
        {
            int l, r, mn = 1e9;
            cin >> l >> r;
            for (int i = 1; i <= 6; i++)
            {
                mn = min(mn, query(i, 1, 1, n, l, r));
            }
            cout << mn << endl;
        }
    }
}

signed main()
{
    srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}