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

· · 题解

珂朵莉树好题！

区间推平往往是珂朵莉树的标志，没学过可以看一下这个大佬的讲解。

注意本题“大小写不敏感”，读入字母时应注意大小写转化。

op == 1

取出区间[L, R]，遍历查找是否有等于k的子区间，有的话就直接加上区间长度。

op == 2

这就是珂朵莉树基本操作assign，在此不再赘述。

op == 3

珂朵莉树的储存方式其实是类似一个桶的，而本题元素只有26个，所以使用桶排要简洁高效的多。

取出区间[L, R]，若此区间值为k，则将B[k]加上区间长度并删除该区间。然后从小到大遍历桶并从L开始往后插入，每一段的长度就是数的个数。

#include <bits/stdc++.h>
#define IT set<Node>::iterator
using namespace std;

int c(char x)
{
    if ('a'<=x && x<='z') return x - 'a';
    return x - 'A';//大小写敏感的转化 
}

struct Node
{
    mutable int L, R, z;
    int operator <(const Node &a) const{
        return L < a.L;
    }
};

set <Node> a;

IT split(int p)
{
    auto it = a.lower_bound(Node{p, 0, 0});
    if (it != a.end() && it->L==p) return it;
    --it;
    Node x = *it; a.erase(it);
    a.insert(Node{x.L, p-1, x.z});
    return a.insert(Node{p, x.R, x.z}).first;
}

int N, M, op, x, y, z, B[27];
char xc;

int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> xc;
        a.insert(Node{i, i, c(xc)});
    }
    for (int i = 1; i <= M; i++)
    {
        cin >> op >> x >> y;
        if (op == 3)
        {
            memset(B, 0, sizeof B);//清空桶 
            auto itr = split(y+1), itl = split(x);
            while (itl != itr)
            {
                B[itl->z] += itl->R - itl->L + 1;
                itl = a.erase(itl);//C++11的erase可以在删除元素后返回下一个元素，省去itl++。 
            }
            for (int i = 0; i < 26; i++)
                if (B[i])
                {
                    a.insert(Node{x, x + B[i]-1, i});//从左端点往后插入 
                    x += B[i];
                }
            continue;
        }
        cin >> xc, z = c(xc);
        if (op == 1)
        {
            int ans = 0;
            auto itr = split(y+1), itl = split(x);
            for (; itl != itr; itl++)
                if (itl->z == z) ans += itl->R - itl->L + 1;//暴力遍历查找 
            printf("%d\n", ans);
        }
        if (op == 2)
        {//珂朵莉树基本操作assign 
            auto itr = split(y+1), itl = split(x);
            a.erase(itl, itr);
            a.insert(Node{x, y, z});
        }
    }
}