洛谷P2787 语文1（chin1）- 理理思维（珂朵莉树）

传送门

一看到区间推倒……推平操作就想到珂朵莉树

区间推平直接assign，查询暴力，排序的话开一个桶统计，然后一个字母一个字母加就好了

开桶统计的时候忘了保存原来的左指针然后挂了233

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<set>

 #define IT set<node>::iterator

 using std::set;

 int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getchar()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getchar());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 const int N=5e4+;

 struct node{

     int l,r;mutable char v;

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

     inline bool operator <(const node &b)const

     {return l<b.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-,v));

     return s.insert(node(pos,r,v)).first;

 }

 void assign(int l,int r,char v){

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

     s.erase(itl,itr),s.insert(node(l,r,v));

 }

 int getcnt(int l,int r,char v){

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

     for(;itl!=itr;++itl) res+=itl->v==v?itl->r-itl->l+:;

     return res;

 }

 int cnt[];

 void sss(int l,int r){

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

     for(IT it=itl;it!=itr;++it) cnt[it->v-'A']+=it->r-it->l+;

     s.erase(itl,itr);int pos=l;

     for(int i=;i<;++i)

     if(cnt[i]){

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

         pos+=cnt[i];cnt[i]=;

     }

 }

 char ch[N];

 int main(){

 //    freopen("testdata.in","r",stdin);

     int n=read(),m=read();scanf("%s",ch+);

     for(int i=;i<=n;++i) ch[i]>'Z'?ch[i]-='a'-'A':,s.insert(node(i,i,ch[i]));

     s.insert(node(n+));

     while(m--){

         int op=read(),l=read(),r=read();

         if(op!=) scanf("%s",ch+),ch[]>'Z'?ch[]-='a'-'A':;

         switch(op){

             case :printf("%d\n",getcnt(l,r,ch[]));break;

             case :assign(l,r,ch[]);break;

             case :sss(l,r);break;

         }

     }

     return Ot(),;

 }