rt，排序用的桶排。

#include <bits/stdc++.h>

#define IT set<node>::iterator
#define int long long
#define N 1000100

using namespace std;

int n, m;
char a[N], cnt[30];
struct node
{
    int l, r;
    mutable char s;
    node(int L, int R = -1, char S = ' '): l(L), r(R), s(S) {}
    bool operator < (const node &o) const{return l < o.l;}
};
set<node> s;

inline int cmp(node a, node b){return a.s < b.s;}

inline char get_A(char w)
{
    char x;
    if(w >= 'a' && w <= 'z') x = w - 'a' + 'A';
    return x;
}

IT split(int p)
{
    IT it = s.lower_bound(node(p));
    if(it != s.end() && it -> l == p) return it;
    it --;
    int L = it -> l, R = it -> r;
    char S = it -> s;
    s.erase(it);
    s.insert(node(L, p - 1, S));
    return s.insert(node(p, R, S)).first;
}

inline void assign(int l, int r, char S)
{
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, S));
    return ;
}

inline int ask(int l, int r, char S)
{
    IT itr = split(r + 1), itl = split(l);
    int res = 0;
    for(; itl != itr; itl ++)
        if(itl -> s == S) res += itl -> r - itl -> l + 1;
    return res;
}

inline void resort(int l, int r)
{
    memset(cnt, 0, sizeof(cnt));
	IT itr = split(r + 1), itl = split(l), it = itl;
	for(; itl != itr ; itl ++)
		cnt[itl -> s - 'A'] += itl -> r - itl -> l + 1;
	s.erase(it, itr);
	for(int i = 0; i < 26; i ++)
    {
		if(cnt[i])
		{
			s.insert(node(l, l + cnt[i] - 1, i + 'A'));
			l += cnt[i];
		}
    }
}

signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        s.insert(node(i, i, toupper(a[i])));
    }
    for(int i = 1; i <= m; i ++)
    {
        int l, r, op;
        char s1;
        cin >> op >> l >> r;
        if(op == 1) cin >> s1, cout << ask(l, r, toupper(s1)) << endl;
        if(op == 2) cin >> s1, assign(l, r, toupper(s1));
        if(op == 3) resort(l, r);
        // for(IT i = s.begin(); i != s.end(); i ++)
            // cout << " L : " << i -> l << "  R : " << i -> r << "  S: " << i -> s << endl;
    }
    return 0;
}