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

Bobi2014 · 2025-08-26 20:50:11 · 题解

这是一道可癌的线段树题目。

前置知识

• 线段树

思路

先把所有字符都变成小写。

这道题线段树节点可以维护每个字符出现的次数之和，操作 1 和 2 是简单的区间查询和区间修改，操作 3 可以转化为区间查询和区间修改，设该区间每个小写字母的出现次数为 cnt_{字符序 - 97}，那么前 cnt_{0} 个位置改成 a，cnt_{0} + 1 到 cnt_{0} + cnt_{1} 改成 b，接下来以此类推。

时间复杂度 O(n \log n)，还有个 26 的常数。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n,Q;
string str;
namespace SegmentTree{
    struct node{
        int cnt[26];
        char tag;
    } tri[N << 2];
    int cnt[26];
    void build(int p,int l,int r){
        if(l == r){
            tri[p].cnt[str[l] - 'a'] ++;
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1,l,mid);
        build(p << 1 | 1,mid + 1,r);
        for(int i = 0;i < 26;i ++){
            tri[p].cnt[i] = tri[p << 1].cnt[i] + tri[p << 1 | 1].cnt[i];
        }
    }
    void pushdown(int p,int l,int r){
        if(tri[p].tag != 0 and l < r){
            int mid = (l + r) >> 1;
            memset(tri[p << 1].cnt,0,sizeof(tri[p << 1].cnt));
            memset(tri[p << 1 | 1].cnt,0,sizeof(tri[p << 1 | 1].cnt));
            tri[p << 1].cnt[tri[p].tag - 'a'] = mid - l + 1;
            tri[p << 1 | 1].cnt[tri[p].tag - 'a'] = r - mid;
            tri[p << 1].tag = tri[p].tag;
            tri[p << 1 | 1].tag = tri[p].tag;
            tri[p].tag = 0;
        }
    }
    void update(int p,int ql,int qr,int l,int r,char c){
        if(ql <= l and r <= qr){
            memset(tri[p].cnt,0,sizeof(tri[p].cnt));
            tri[p].cnt[c - 'a'] = r - l + 1;
            tri[p].tag = c;
            return;
        }
        pushdown(p,l,r);
        int mid = (l + r) >> 1;
        if(ql <= mid){
            update(p << 1,ql,qr,l,mid,c);
        }
        if(qr > mid){
            update(p << 1 | 1,ql,qr,mid + 1,r,c);
        }
        for(int i = 0;i < 26;i ++){
            tri[p].cnt[i] = tri[p << 1].cnt[i] + tri[p << 1 | 1].cnt[i];
        }
    }
    void query(int p,int ql,int qr,int l,int r){
        if(ql <= l and r <= qr){
            for(int i = 0;i < 26;i ++){
                cnt[i] += tri[p].cnt[i];
            }
            return;
        }
        pushdown(p,l,r);
        int mid = (l + r) >> 1;
        if(ql <= mid){
            query(p << 1,ql,qr,l,mid);
        }
        if(qr > mid){
            query(p << 1 | 1,ql,qr,mid + 1,r);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> Q >> str;
    str = ' ' + str;
    for(int i = 1;i <= n;i ++){
        str[i] = tolower(str[i]);
    }
    SegmentTree::build(1,1,n);
    while(Q --){
        int op;
        cin >> op;
        if(op == 1){
            int l,r;
            char c;
            cin >> l >> r >> c;
            c = tolower(c);
            memset(SegmentTree::cnt,0,sizeof(SegmentTree::cnt));
            SegmentTree::query(1,l,r,1,n);
            cout << SegmentTree::cnt[c - 'a'] << '\n';
        }else if(op == 2){
            int l,r;
            char c;
            cin >> l >> r >> c;
            c = tolower(c);
            SegmentTree::update(1,l,r,1,n,c);
        }else{
            int l,r;
            cin >> l >> r;
            memset(SegmentTree::cnt,0,sizeof(SegmentTree::cnt));
            SegmentTree::query(1,l,r,1,n);
            int pos = l;
            for(int i = 0;i < 26;i ++){
                if(SegmentTree::cnt[i] > 0){
                    SegmentTree::update(1,pos,pos + SegmentTree::cnt[i] - 1,1,n,i + 'a');
                    pos += SegmentTree::cnt[i];
                }
            }
        }
    }
    return 0;
}