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

SuperJvRuo · 2018-10-05 14:52:45 · 题解

用std::set实现的珂朵莉树才是正统，链表什么的都是异端。不会珂朵莉树的可以点前面的链接或者看本人在CF896C的题解。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<set>

int Read()
{
    int x=0;char c=getchar();
    while(!isdigit(c))
    {
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}

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;
    }
};

using std::set;

set<node> s;

#define IT set<node>::iterator
//split(pos)操作是指将原来含有pos位置的节点分成两部分：[l,pos−1][pos,r]
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, 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 key)
{
    IT itr=split(r+1),itl=split(l);
    int res=0;
    for(;itl!=itr;++itl)
    {
        if(itl->v==key)
        {
            res+=itl->r-itl->l+1;
        }
    }
    return res;
}

//珂朵莉树经典的区间赋值
void replace(int l,int r,char key)
{
    IT itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,key));
}

//开个桶，遍历一遍然后insert进去
void sort_range(int l,int r)
{
    int cnt[27];
    memset(cnt,0,sizeof(cnt));
    IT itr=split(r+1),itl=split(l);
    for(IT itl2=itl;itl2!=itr;++itl2)
    {
        cnt[itl2->v-'A']+=itl2->r-itl2->l+1;
    }
    s.erase(itl,itr);
    int pos=l;
    for(int i=0;i<26;++i)
    {
        if(cnt[i])
        {
            s.insert(node(pos,pos+cnt[i]-1,i+'A'));
            pos+=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(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));
    s.insert(node(n+1,n+100,0));
    int opt,x,y;
    char letter[5];
    while(m--)
    {
        opt=Read();
        if(opt==1)
        {
            x=Read(),y=Read();
            scanf("%s",letter);
            printf("%d\n",count(x,y,toupper(letter[0])));
        }
        else if(opt==2)
        {
            x=Read(),y=Read();
            scanf("%s",letter);
            replace(x,y,toupper(letter[0]));
        }
        else
        {
            x=Read(),y=Read();
            sort_range(x,y);
        }
    }
    return 0;
}