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

· · 题解

发现题解区的线段树题解都是建 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;
}