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

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

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

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

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<set>
 5 #define IT set<node>::iterator
 6 using std::set;
 7 int read(){
 8     #define num ch-'0'
 9     char ch;bool flag=0;int res;
10     while(!isdigit(ch=getchar()))
11     (ch=='-')&&(flag=true);
12     for(res=num;isdigit(ch=getchar());res=res*10+num);
13     (flag)&&(res=-res);
14     #undef num
15     return res;
16 }
17 char sr[1<<21],z[20];int C=-1,Z;
18 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
19 void print(int x){
20     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
21     while(z[++Z]=x%10+48,x/=10);
22     while(sr[++C]=z[Z],--Z);sr[++C]='
';
23 }
24 const int N=5e4+5;
25 struct node{
26     int l,r;mutable char v;
27     node(int L,int R=-1,char V=-1):l(L),r(R),v(V){}
28     inline bool operator <(const node &b)const
29     {return l<b.l;}
30 };set<node> s;
31 IT split(int pos){
32     IT it=s.lower_bound(node(pos));
33     if(it!=s.end()&&it->l==pos) return it;
34     --it;int l=it->l,r=it->r;char v=it->v;
35     s.erase(it),s.insert(node(l,pos-1,v));
36     return s.insert(node(pos,r,v)).first;
37 }
38 void assign(int l,int r,char v){
39     IT itr=split(r+1),itl=split(l);
40     s.erase(itl,itr),s.insert(node(l,r,v));
41 }
42 int getcnt(int l,int r,char v){
43     IT itr=split(r+1),itl=split(l);int res=0;
44     for(;itl!=itr;++itl) res+=itl->v==v?itl->r-itl->l+1:0;
45     return res;
46 }
47 int cnt[26];
48 void sss(int l,int r){
49     IT itr=split(r+1),itl=split(l);
50     for(IT it=itl;it!=itr;++it) cnt[it->v-'A']+=it->r-it->l+1;
51     s.erase(itl,itr);int pos=l;
52     for(int i=0;i<26;++i)
53     if(cnt[i]){
54         s.insert(node(pos,pos+cnt[i]-1,i+'A'));
55         pos+=cnt[i];cnt[i]=0;
56     }
57 }
58 char ch[N];
59 int main(){
60 //    freopen("testdata.in","r",stdin);
61     int n=read(),m=read();scanf("%s",ch+1);
62     for(int i=1;i<=n;++i) ch[i]>'Z'?ch[i]-='a'-'A':0,s.insert(node(i,i,ch[i]));
63     s.insert(node(n+1));
64     while(m--){
65         int op=read(),l=read(),r=read();
66         if(op!=3) scanf("%s",ch+1),ch[1]>'Z'?ch[1]-='a'-'A':0;
67         switch(op){
68             case 1:printf("%d
",getcnt(l,r,ch[1]));break;
69             case 2:assign(l,r,ch[1]);break;
70             case 3:sss(l,r);break;
71         }
72     }
73     return Ot(),0;
74 }