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

览遍千秋 · 2019-11-06 06:46:32 · 题解

珂朵莉树大法好

珂朵莉树是一种基于 set 的暴力数据结构。

其核心思想是不用的区间就存在 set 里，到用的时候再把它拆开来用。

推荐一个非常棒的讲解珂朵莉树的博客：https://www.cnblogs.com/yzhang-rp-inf/p/9443659.html

就本题来说

• 操作1：珂朵莉树暴力拆开区间 [l,r] ，遍历统计

• 操作2：珂朵莉树 assign 操作

• 操作3：拆开区间 [l,r] ，桶排后再 assign 回去

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

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 < (node a) const {
        return l<a.l;
    }
};

set<node>s;
#define IT set<node>::iterator

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

void assign(int l,int r,char val){
    IT rr=split(r+1),ll=split(l);
    s.erase(ll,rr);s.insert(node(l,r,val));
}

void sort(int l,int r){
    IT rr=split(r+1),ll=split(l);IT it=ll;
    int cnt[27];memset(cnt,0,sizeof(cnt));
    for(;ll!=rr;++ll){
        cnt[ll->v-'A']+=ll->r-ll->l+1;
    }
    s.erase(it,rr);
    int L=l;
    for(int i=0;i<26;i++){
        if(!cnt[i]) continue;
//      assign(L,L+cnt[i]-1,(char)(i+'A'-1));
        s.insert(node(L,L+cnt[i]-1,(char)(i+'A')));
        L=L+cnt[i];
    }
}

int sum(int l,int r,char val){
    int res=0;
    IT rr=split(r+1),ll=split(l);
    for(;ll!=rr;++ll){
        if(ll->v==val) res+=ll->r-ll->l+1;
    }
    return res;
}

int n,m;
char ss[50007],c;
int op,l,r;
int main(){
    scanf("%d%d%s",&n,&m,ss+1);
    for(int i=1;i<=n;i++){
        ss[i]=toupper(ss[i]);
        s.insert(node(i,i,ss[i]));
    }
    while(m--){
        read(op);read(l);read(r);
        if(op==1){
            cin>>c;
            printf("%d\n",sum(l,r,toupper(c)));
        }
        else if(op==2){
            cin>>c;
            assign(l,r,toupper(c));
        }
        else sort(l,r);
    }
    return 0;
}