【题解】Luogu P2787 语文1（chin1）- 理理思维

原题传送门：P2787 语文1（chin1）- 理理思维

前置芝士：珂朵莉树

窝博客里对珂朵莉树的介绍

没什么好说的自己看看吧

珂朵莉树跑的飞快，但还是没有memset0小姐姐跑得快

操作1：暴力统计出奇迹

操作2：推平区间，珂朵莉树基本操作

操作3：排序区间，我就写了一个桶排

窝一开始头文件直接用bits出玄学ce

toupper是把小写转大写，以防数据出锅

#pragma GCC optimize("O3")

#include<cstdio>

#include<cctype>

#include<cstring>

#include<set>

#define IT set<node>::iterator

using namespace std;

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

struct node

{

    int l,r;

    mutable char v;

    node(int L, int R=-1, char V=0):l(L), r(R), v(V) {}

    bool operator<(const node& o) const

    {

        return l < o.l;

    }

};

set<node> s;

IT split(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;

	char V = it->v;

    s.erase(it);

    s.insert(node(L, pos-1, V));

    return s.insert(node(pos, R, V)).first;

}

int count(int l,int r,char v)

{

	IT itr = split(r+1) ,itl = split(l);

	int ans=0;

	for( ; itl != itr ; ++itl)

		if(itl->v == v)

			ans+=itl->r-itl->l+1;

	return ans;

}

void assign_val(int l,int r,char v)

{

    IT itr = split(r+1),itl = split(l);

    s.erase(itl, itr);

    s.insert(node(l, r, v));

}

void sort_val(int l,int r)

{

	int cnt[27];

    memset(cnt,0,sizeof(cnt));

	IT itr = split(r+1), itl = split(l), it = itl;

	for( ; itl != itr ; ++itl)

		cnt[itl->v-'A']+=itl->r-itl->l+1;

	s.erase(it,itr);

	for(register int i=0;i<26;++i)

		if(cnt[i])

		{

			s.insert(node(l,l+cnt[i]-1,i+'A'));

			l+=cnt[i];

		}

}

char str[50005];

int main()

{

	int n=read(),m=read();

	scanf("%s",str+1);

	int cnt=1;

	char last=toupper(str[1]);

	for(register 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 opt=read(),l=read(),r=read();

		char dic[5];

		if(opt==1)

		{

			scanf("%s",dic);

			printf("%d\n",count(l,r,toupper(dic[0])));

		}

		else if(opt==2)

		{

			scanf("%s",dic);

			assign_val(l,r,toupper(dic[0]));

		}

		else

			sort_val(l,r);

	}

	return 0;

 }