洛谷 2787 理理思维

看到区间推平就想到珂朵莉树。 由于相对暴力，可以实现很多操作。

对于排序操作，观察到值域非常小，所以可以桶排。

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <set>
#include <algorithm>
using namespace std;
const int N = 5e4;
int n,m;
char a[N + 10];
struct node
{
    int l,r;
    mutable char val;
    inline bool operator<(const node &a) const
    {
        return l < a.l;
    }
};
set<node> tree;
typedef set<node>::iterator IT;
IT split(int x)
{
    IT it = tree.lower_bound((node){x,0,0});
    if(it != tree.end() && it->l == x)
        return it;
    --it;
    int l = it->l,r = it->r;
    char v = it->val;
    tree.erase(it);
    tree.insert((node){l,x - 1,v});
    return tree.insert((node){x,r,v}).first;
}
inline void assign(int l,int r,char val)
{
    IT itr = split(r + 1),itl = split(l);
    tree.erase(itl,itr);
    tree.insert((node){l,r,val});
}
inline void sort_val(int l,int r)
{
    IT itr = split(r + 1),itl = split(l);
    int buc[30];
    memset(buc,0,sizeof buc);
    IT it = itl;
    for(;itl != itr;++itl)
        buc[itl->val - 'A'] += itl->r - itl->l + 1;
    tree.erase(it,itr);
    for(register int i = 0;i < 26;++i)
        if(buc[i])
            tree.insert((node){l,l + buc[i] - 1,'A' + i}),l += buc[i];
}
inline int count_val(int l,int r,char val)
{
    IT itr = split(r + 1),itl = split(l);
    int ret = 0;
    for(;itl != itr;++itl)
        if(itl->val == val)
            ret += itl->r - itl->l + 1;
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",a + 1);
    char last = toupper(a[1]);
    int cnt = 1;
    for(register int i = 2;i <= n;++i)
        if(toupper(a[i]) == last)
            ++cnt;
        else
        {
            tree.insert((node){i - cnt,i - 1,last});
            last = toupper(a[i]);
            cnt = 1;
        }
    tree.insert((node){n - cnt + 1,n,last});
    int op,l,r;
    char x;
    while(m--)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op == 1)
        {
            scanf(" %c",&x);
            printf("%d\n",count_val(l,r,toupper(x)));
        }
        else if(op == 2)
        {
            scanf(" %c",&x);
            assign(l,r,toupper(x));
        }
        else
            sort_val(l,r);
    }
}