P2787 语文1（chin1）- 理理思维

题目链接：

排序直接桶排序就行了

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define pb push_back
#define fi first
#define se second
const int N=3e6+10;
const int mod=998244353;
void read(int &a)
{
    a=0;int d=1;char ch;
    while(ch=getchar(),ch>'9'||ch<'0')
        if(ch=='-')
            d=-1;
    a=ch^48;
    while(ch=getchar(),ch>='0'&&ch<='9')
        a=(a<<3)+(a<<1)+(ch^48);
    a*=d;
}
int vis[30];
struct note
{
    int l,r;
    mutable char v;
    note(int L,int R=-1,char V=' '){l=L,r=R,v=V;}
    bool operator < (const note &x) const
    {
        return l<x.l;
    }
};
set <note> s;
set <note> :: iterator split(int pos)
{
    auto it=s.lower_bound(note(pos));
    if(it!=s.end()&&it->l==pos) return it;
    it--;
    if(it->r<pos) return s.end();
    int L=it->l,R=it->r;
    char V=it->v;
    s.erase(it);
    s.insert(note(L,pos-1,V));
    return s.insert(note(pos,R,V)).fi;
}
void modify(int l,int r,char v)
{
    auto it2=split(r+1),it1=split(l);
    s.erase(it1,it2);
    s.insert(note(l,r,v));
}
int query(int l,int r,char v)
{
    int ans=0;
    auto it2=split(r+1),it1=split(l);
    for(;it1!=it2;it1++) it1->v==v?ans+=it1->r-it1->l+1:0;
    return ans;
}
void sorted(int l,int r)
{
    memset(vis,0,sizeof(vis));
    auto it2=split(r+1),it1=split(l),it=it1;
    for(;it1!=it2;it1++) vis[it1->v-'A']+=it1->r-it1->l+1;
    s.erase(it,it2);
    int x=l;
    for(re int i=0;i<26;i++)
    {
        if(vis[i])
        {
            s.insert(note(x,x+vis[i]-1,i+'A'));
            x=x+vis[i];
        }
    }
}
int main()
{
    int n,m;
    read(n),read(m);
    char ch;
    for(re int i=1;i<=n;i++) scanf(" %c",&ch),ch=toupper(ch),s.insert(note(i,i,ch));
    for(re int i=1,op,x,y;i<=m;i++)
    {
        read(op),read(x),read(y);
        if(op==1) scanf(" %c",&ch),ch=toupper(ch),printf("%d
",query(x,y,ch));
        else if(op==2) scanf(" %c",&ch),ch=toupper(ch),modify(x,y,ch);
        else sorted(x,y);
    }
    return 0;
}