{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/7mjbtdss %}
发现题解区的线段树题解都是建 $26$ 棵线段树的方法，来一个不建 $26$ 棵线段树的线段树题解。本题思路其实来源于上课老师讲了这题，并且用的是本题解的方法。
思路： #
线段树。
本题除了操作三以外是模版，本题解主要讲操作三，没学过线段树出门右转线段树模版。
我们知道线段树把区间全部修改成同一个值是很简单的，但是本题操作三是要求排序，很可能是修改成不同的值，怎么办呢？我们可以想到既然是要求排序，那么排序后的值是不是连续的，既然是连续的，那是不是可以把它转换为一个普通的区间修改。
考虑把要排序的范围里的所有字母的数量求出来，然后按顺序枚举每个字母，确定排序后被排到了哪个范围，然后正常区间修改就好了。
如何确定被排序后在哪个范围内？首先设现在的起点为 $st$，有 $num$ 个这个字母，那么修改的这个区间大小也是 $num$，但是因为起点也算是占了区间的一个大小，所以终点是 $st+num-1$。
完整代码： #
// 本代码经过 devc++ 自带的格式化格式化
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
struct node {
int cnt[40];// 保存字母出现个数
int tag;// 懒标记标记要换成什么字母
int l,r;
node()
{
l=r=0;
tag=-1;
memset(cnt,0,sizeof cnt);
}
} tree[(55000)*4];
int n,m;
string s;
int op;
int x,y;
char k;
int cnt[40];// 保存字母出现个数，用于操作三，定义全局变量，函数内也可以访问
int szid(char s)
{
return toupper(s)-'A'; // 把字母转换为 cnt 内对应下标
}
void push_up(int now)
{
for(int i=0; i<=27; i++) {
tree[now].cnt[i]=tree[now*2].cnt[i]+tree[now*2+1].cnt[i];
}
return;
}
void push_down(int now)
{
if(tree[now].tag!=-1) {
memset(tree[now*2].cnt,0,sizeof tree[now*2].cnt);
memset(tree[now*2+1].cnt,0,sizeof tree[now*2+1].cnt);
tree[now*2+1].tag=tree[now*2].tag=tree[now].tag;
tree[now*2+1].cnt[tree[now].tag]=tree[now*2+1].r-tree[now*2+1].l+1;
tree[now*2].cnt[tree[now].tag]=tree[now*2].r-tree[now*2].l+1;
tree[now].tag=-1;
}
}
void build(int now,int l,int r)
{
if(l>r)return;
tree[now].l=l;
tree[now].r=r;
if(l==r) {
tree[now].cnt[szid(s[l])]++;
return;
}
int mid=(l+r)>>1;
build(now*2,l,mid);
build(now*2+1,mid+1,r);
push_up(now);
return;
}
void query_cx(int now,int nl,int nr)
{
int l=tree[now].l,r=tree[now].r;
if(nl<=l&&nr>=r) {
for(int i=0; i<=27; i++) {
cnt[i]+=tree[now].cnt[i];
}
return;
}
push_down(now);
int mid=(l+r)>>1;
if(mid>=nl)query_cx(now*2,nl,nr);// l,mid
if(mid<nr)query_cx(now*2+1,nl,nr);// mid+1 r
return;
}
void change(int now,int nl,int nr,int k)
{
int l=tree[now].l,r=tree[now].r;
if(nl<=l&&nr>=r) {
memset(tree[now].cnt,0,sizeof tree[now].cnt);
tree[now].cnt[k]=r-l+1;
tree[now].tag=k;
return;
}
push_down(now);
int mid=(l+r)>>1;
if(mid>=nl)change(now*2,nl,nr,k);
if(mid<nr)change(now*2+1,nl,nr,k);
push_up(now);
return;
}
void change_px(int nl,int nr)
{
int start=nl;
for(int i=0; i<=27; i++) {
if(cnt[i]==0)continue;
change(1,start,start+cnt[i]-1,i);// 确定修改范围，使用 change 函数
start+=cnt[i];// 更新起点
}
return;
}
int query(int now,int nl,int nr,int k)
{
int l=tree[now].l,r=tree[now].r;
if(nl<=l&&nr>=r) {
return tree[now].cnt[k];
}
push_down(now);
int mid=(l+r)>>1;
int ans=0;
if(mid>=nl)ans+=query(now*2,nl,nr,k);// l,mid
if(mid<nr)ans+=query(now*2+1,nl,nr,k);// mid+1 r
return ans;
}
int main()
{
cin>>n>>m>>s;
s=" "+s;
build(1,1,n);
while(m--) {
cin>>op;
if(op==1) {
cin>>x>>y>>k;
cout<<query(1,x,y,szid(k))<<"\n";
} else if(op==2) {
cin>>x>>y>>k;
change(1,x,y,szid(k));
} else {
cin>>x>>y;
memset(cnt,0,sizeof cnt);
query_cx(1,x,y);// 查询每个字母出现的次数
change_px(x,y);
}
}
return 0;
}