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

· · 题解

1. 题意解释

给出一个字符串，你可以对其进行以下三种操作：

  1. 获取第 x 到第 y 个字符中字母 k 出现了多少次。

  2. 将第 x 到第 y 个字符全部赋值为字母 k。

  3. 将第 x 到第 y 个字符按照 a∼z 的顺序排序。

2. 题意解释

把字符串看错一个由字符组成的数组，这道题就成了区间覆盖+区间排序问题。

容易想到用线段树解决。

每个线段维护一个 cnt 数组和 tag 标记，cnt_i 表示第 i 个字母出现的次数，tag 表示这个区间内的所有字母都为同一个值，即编号为 tag 的字母。

这样一来操作一和操作二就是区间查询和区间覆盖，重点考虑操作三。

由于值域是有限的，我们不难想到桶排序。

而且我们的线段树已经维护了区间内的桶。

于是我们也就可以区间查询+区间覆盖解决区间排序问题。

到现在，这道题就成线段树板子题了。

不理解的同学看代码注释噻。

3. 代码实现

一个需要注意的点：输入中可能同时出现大小写字母，记住把它们全部转化为统一的大写或小写！

AC code：

#include<bits/stdc++.h>
using namespace std;
int n,m,op,x,y;
char k;
string s;
struct segtree{
    int l,r,cnt[30],tag;
}t[200200];
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r,t[p].tag=0;
    if(l==r){
        t[p].cnt[s[l-1]-'A'+1]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    for(int i=1;i<=26;i++){
        t[p].cnt[i]=t[p*2].cnt[i]+t[p*2+1].cnt[i];
    }
}
void pushdown(int p){//懒标记下传
    if(t[p].tag){
        t[p*2].cnt[t[p].tag]=t[p*2].r-t[p*2].l+1;
        t[p*2+1].cnt[t[p].tag]=t[p*2+1].r-t[p*2+1].l+1;//子节点计数更新，将编号为 tag 的字母数更新为区间长度（因为区间被这个字母覆盖了）
        for(int i=1;i<=26;i++){
            if(i!=t[p].tag){
                t[p*2].cnt[i]=0;
                t[p*2+1].cnt[i]=0;
            }
        }////子节点计数更新，其余字母数量全部为0
        t[p*2].tag=t[p].tag;
        t[p*2+1].tag=t[p].tag;//标记下传
        t[p].tag=0;//父节点标记清空
    }
}
void change(int p,int l,int r,int c){//区间覆盖
    if(l>r){
        return ;
    }
    if(l<=t[p].l&&t[p].r<=r){
        t[p].tag=c;
        t[p].cnt[c]=t[p].r-t[p].l+1;
        for(int i=1;i<=26;i++){
            if(i!=c){
                t[p].cnt[i]=0;
            }
        }//更新标记和计数，原有的标记直接覆盖
        return ; 
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid){
        change(p*2,l,r,c);
    }
    if(r>mid){
        change(p*2+1,l,r,c);
    } 
    for(int i=1;i<=26;i++){
        t[p].cnt[i]=t[p*2].cnt[i]+t[p*2+1].cnt[i];
    }
}
int ask(int p,int l,int r,int c){//区间查询
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].cnt[c];
    }
    pushdown(p); 
    int mid=(t[p].l+t[p].r)>>1,val=0;
    if(l<=mid){
        val+=ask(p*2,l,r,c);
    }
    if(r>mid){
        val+=ask(p*2+1,l,r,c);
    }
    return val;
}
int main(){
    cin>>n>>m;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]>='a'&&s[i]<='z'){
            s[i]=s[i]+'A'-'a';
        }
    }//记得把字符串统一转换为大写或小写，我这里用的是大写
    build(1,1,n);
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            if(k>='a'&&k<='z'){
                k=k+'A'-'a';//把字母转换为大写
            }
            cout<<ask(1,x,y,k-'A'+1)<<endl;
        }
        if(op==2){
            cin>>x>>y>>k;
            if(k>='a'&&k<='z'){
                k=k+'A'-'a';//把字母转换为大写
            }
            change(1,x,y,k-'A'+1);
        }
        if(op==3){
            cin>>x>>y;
            int num[30];
            memset(num,0,sizeof num);
            for(int i=1;i<=26;i++){
                num[i]=num[i-1]+ask(1,x,y,i);
            }//查询前i个字母的数量总和，方便下面更新
            for(int i=1;i<=26;i++){
                change(1,x+num[i-1],x+num[i]-1,i);
            }//更新整个区间内的字母，第i个字母的范围为x+num[i-1]至x+num[i]-1
        }
    }
    return 0;
}