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

用```std::set```实现的[珂朵莉树](https://www.luogu.org/blog/ACdreamer/chtholly-tree)才是正统，链表什么的都是异端。不会珂朵莉树的可以点前面的链接或者看本人在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; } ```