题

提交记录

#include<bits/stdc++.h>
#define IT set<node>::iterator 
#define int long long
#define gc getchar()
#define rd read()
#define N 50005
using namespace std;
inline int read()
{
	register int x=0,ss=1;
	register char s=gc;
	while(!isdigit(s)&&s!='-')s=gc;
	if(s=='-')ss*=-1,s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=gc;
	return ss*x;
}
struct node
{
	int l,r;
	mutable char x;
	node(int L,int R=-1,char X=0): l(L),r(R),x(X){}
	bool operator<(const node &o)const 
	{
	    return l < o.l;
	}
};set<node> s;
IT spilit(int pos)
{
	IT it=s.lower_bound(node(pos));
	if(it!=s.end()&&it->l==pos)return it;
	it--;
	int L=it->l,R=it->r,V=it->x;
	s.erase(it);
	s.insert(node(L,pos-1,V));
	return s.insert(node(pos,R,V)).first;
}
void assign_val(int l,int r,char val)
{
	IT itl=spilit(l),itr=spilit(r+1);
	s.erase(itl,itr);
	s.insert(node(l,r,val));
}
int ask(int l,int r,char k)
{
	int sum=0;
	IT itl=spilit(l),itr=spilit(r+1);
	for(;itl!=itr;itl++)
	{
		if(itl->x==k)sum+=(itl->r-itl->l+1);
	}
	return sum;
} 
void sortt(int l,int r)
{
	IT itl=spilit(l),itr=spilit(r+1),it=itl;
	int cnt[27]={0};
	for(;itl!=itr;itl++)cnt[itl->x-'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];
		}
	}
}
int n,m;
int vis[N];
char str[N];
signed main()
{
	n=rd,m=rd;
	cin>>str+1;
	char last=toupper(str[1]);
	int cnt=1;
	for(int i=2;i<=n;++i)
	{
		str[i]=toupper(str[i]);
		if(str[i]==last)
			++cnt;
		else
		{
			s.insert(node(i-cnt,i-1,last));
			last=str[i];
			cnt=1;
		}
	}
	s.insert(node(n+1-cnt,n,last));
	while(m--)
	{
		int op=rd,l=rd,r=rd;
		char dic[5];
		if(op==1)
		{
			cin>>dic;
			cout<<ask(l,r,dic[0])<<endl;
		}
		if(op==2)
		{
			cin>>dic;
			assign_val(l,r,dic[0]);
		}
		if(op==3)sortt(l,r);
	}
	return 0;
}