rt

#include<bits/stdc++.h>
#define M 300001
#define ls p<<1
#define rs p<<1|1
using namespace std;
inline int read()
{
	int k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
int n,Q;
char ch;
struct tree
{
	int val[M<<2],tag[M<<2];
	inline void push_up(int p)
	{
		val[p]=val[ls]+val[rs];
		return;
	}
	inline void push_down(int p,int l,int r)
	{
		int mid=(l+r)>>1;
		if(tag[p])
		{
			tag[ls]=tag[rs]=tag[p];
			if(tag[p]>0) val[ls]=mid-l+1,val[rs]=r-mid;
			else val[ls]=0,val[rs]=0;
			tag[p]=0;
		}
		return;
	}
	inline void modify(int p,int l,int r,int st,int en,int k)
	{
		if(st<=l&&r<=en)
		{
			if(k>0) val[p]=r-l+1,tag[p]=1;
			else val[p]=0,tag[p]=-1;
			return;
		}
		push_down(p,l,r);
		int mid=(l+r)>>1;
		if(st<=mid)  modify(ls,l,mid,st,en,k);
		if(en>mid) modify(rs,mid+1,r,st,en,k);
		push_up(p);
	}
	inline int query(int p,int l,int r,int st,int en)
	{
		if(st<=l&&r<=en) return val[p];
		push_down(p,l,r);
		int mid=(l+r)>>1,res=0;
		if(st<=mid)  res+=query(ls,l,mid,st,en);
		if(en>mid) res+=query(rs,mid+1,r,st,en);
		return res;
	}
}t[30];
int main()
{
	n=read(),Q=read();
	for(int i=1;i<=n;i++)
	{
		scanf("%c",&ch);
		if('A'<=ch&&ch<='Z') ch=ch-'A'+'a';
		int pos=ch-'a';
		t[pos].modify(1,1,n,i,i,1);
	}
	while(Q--)
	{
		int opt=read(),st=read(),en=read();
		if(st>en) swap(st,en);
		if(opt==1)
		{
			scanf("%c",&ch);
			if('A'<=ch&&ch<='Z') ch=ch-'A'+'a';
			int pos=ch-'a';
			printf("%d\n",t[pos].query(1,1,n,st,en));
		}
		else if(opt==2)
		{
			scanf("%c",&ch);
			if('A'<=ch&&ch<='Z') ch=ch-'A'+'a';
			int pos=ch-'a';
			for(int i=0;i<=25;i++)
				if(i!=pos) t[i].modify(1,1,n,st,en,-1);
			t[pos].modify(1,1,n,st,en,1);
		}
		else
		{
			int last=st,num=0;
			for(int pos=0;pos<=25;pos++)
			{
				num=t[pos].query(1,1,n,st,en),t[pos].modify(1,1,n,st,en,-1);
				if(num) t[pos].modify(1,1,n,last,last+num-1,1),last+=num;
			}
		}
	}
	return 0;
}

scanf版

#include<bits/stdc++.h>
#define M 300001
#define ls p<<1
#define rs p<<1|1
using namespace std;
inline int read()
{
	int k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
int n,Q;
char ch;
struct tree
{
	int val[M<<2],tag[M<<2];
	inline void push_up(int p)
	{
		val[p]=val[ls]+val[rs];
		return;
	}
	inline void push_down(int p,int l,int r)
	{
		int mid=(l+r)>>1;
		if(tag[p])
		{
			tag[ls]=tag[rs]=tag[p];
			if(tag[p]>0) val[ls]=mid-l+1,val[rs]=r-mid;
			else val[ls]=0,val[rs]=0;
			tag[p]=0;
		}
		return;
	}
	inline void modify(int p,int l,int r,int st,int en,int k)
	{
		if(st<=l&&r<=en)
		{
			if(k>0) val[p]=r-l+1,tag[p]=1;
			else val[p]=0,tag[p]=-1;
			return;
		}
		push_down(p,l,r);
		int mid=(l+r)>>1;
		if(st<=mid)  modify(ls,l,mid,st,en,k);
		if(en>mid) modify(rs,mid+1,r,st,en,k);
		push_up(p);
	}
	inline int query(int p,int l,int r,int st,int en)
	{
		if(st<=l&&r<=en) return val[p];
		push_down(p,l,r);
		int mid=(l+r)>>1,res=0;
		if(st<=mid)  res+=query(ls,l,mid,st,en);
		if(en>mid) res+=query(rs,mid+1,r,st,en);
		return res;
	}
}t[30];
int main()
{
	n=read(),Q=read();
	for(int i=1;i<=n;i++)
	{
		cin>>ch;
		if('A'<=ch&&ch<='Z') ch=ch-'A'+'a';
		int pos=ch-'a';
		t[pos].modify(1,1,n,i,i,1);
	}
	while(Q--)
	{
		int opt=read(),st=read(),en=read();
		if(st>en) swap(st,en);
		if(opt==1)
		{
			cin>>ch;
			if('A'<=ch&&ch<='Z') ch=ch-'A'+'a';
			int pos=ch-'a';
			printf("%d\n",t[pos].query(1,1,n,st,en));
		}
		else if(opt==2)
		{
			cin>>ch;
			if('A'<=ch&&ch<='Z') ch=ch-'A'+'a';
			int pos=ch-'a';
			for(int i=0;i<=25;i++)
				if(i!=pos) t[i].modify(1,1,n,st,en,-1);
			t[pos].modify(1,1,n,st,en,1);
		}
		else
		{
			int last=st,num=0;
			for(int pos=0;pos<=25;pos++)
			{
				num=t[pos].query(1,1,n,st,en),t[pos].modify(1,1,n,st,en,-1);
				if(num) t[pos].modify(1,1,n,last,last+num-1,1),last+=num;
			}
		}
	}
	return 0;
}

cin版