洛谷P2787

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<cstring>
#define Set set<Node>::iterator
using namespace std;
struct Node
{
    int l,r;
    mutable char val;
    Node(int L,int R,char V):l(L),r(R),val(V){}
    Node(int L):l(L){}
    bool operator < (const Node &it)const
    {
        return l<it.l;
    }
};
set<Node> st;
int n,m;
int c[26];
Set Split(int x)
{
    Set it=st.lower_bound(Node(x));
    if(it!=st.end()&&it->l==x)
        return it;
    --it;
    int L=it->l,R=it->r;
    char V=it->val;
    st.erase(it);
    st.insert(Node(L,x-1,V));
    return st.insert(Node(x,R,V)).first;
}
void Change(int l,int r,char v)
{
    Set rr=Split(r+1),ll=Split(l);
    st.erase(ll,rr);
    st.insert(Node(l,r,v));
}
int Search(int l,int r,char v)
{
	Set rr=Split(r+1),ll=Split(l);
	int ans=0;
	for(Set it=ll;it!=rr;++it)
		if(it->val==v)
			ans+=it->r-it->l+1;
	return ans;
}
void Sort(int l,int r)
{
	memset(c,0,sizeof(c));
	Set rr=Split(r+1),ll=Split(l);
	for(Set it=ll;it!=rr;++it)
		c[it->val-‘A‘]+=it->r-it->l+1;
	st.erase(ll,rr);
	int now=l;
	for(int i=0;i<26;++i)
		if(c[i])
		{
			st.insert(Node(now,now+c[i]-1,i+‘A‘));
			now=now+c[i];
		}
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
    	char in;
    	scanf(" %c",&in);
    	if(in>=‘a‘&&in<=‘z‘)
    		in=in-‘a‘+‘A‘;
    	st.insert(Node(i,i,in));
	}
	st.insert(Node(n+1));
	for(int i=1;i<=m;++i)
	{
		int opt,l,r;
		char k;
		scanf("%d%d%d",&opt,&l,&r);
		if(opt==1)
		{
			scanf(" %c",&k);
			if(k>=‘a‘&&k<=‘z‘)
    			k=k-‘a‘+‘A‘;
			printf("%d\n",Search(l,r,k));
		}
		if(opt==2)
		{
			scanf(" %c",&k);
			if(k>=‘a‘&&k<=‘z‘)
    			k=k-‘a‘+‘A‘;
			Change(l,r,k);
		}
		if(opt==3)
			Sort(l,r);
	}
    return 0;
}