题意简述

维护字符串，支持以下操作：

• 0 l r k：求l~r中k的出现次数
• 1 l r k：将l~r中元素赋值为k
• 2 l r：询问l~r中最大连续1的长度

题解思路

珂朵莉树暴力赋值，排序，查询

代码

#include <set>
#include <iostream>
#define IT std::set<Node>::iterator
int n,m,opt,l,r,c[26];
char ch;
struct Node {
    int l,r,v;
    Node(const int& L,const int& R,const int& V):l(L),r(R),v(V) {}
    bool operator <(const Node& x) const { return l<x.l; };
};
std::set<Node> s;
inline int read_char() {
    std::cin>>ch; return ch>'Z'?ch-'a':ch-'A';
}
inline IT split(const int& x) {
    IT it=s.lower_bound(Node(x,0,0));
    if (it!=s.end()&&it->l==x) return it;
    --it; int L=it->l,R=it->r,V=it->v; s.erase(it);
    s.insert(Node(L,x-1,V)); return s.insert(Node(x,R,V)).first;
}
inline void assign(const int& l,const int& r,const int& v) {
    IT itr=split(r+1),itl=split(l);
    s.erase(itl,itr); s.insert(Node(l,r,v));
}
inline void sort(int l,const int& r) {
    IT itr=split(r+1),itl=split(l);
    for (register IT it=itl;it!=itr;++it) c[it->v]+=it->r-it->l+1;
    s.erase(itl,itr);
    for (register int i=0;i<26;++i)
        if (c[i]) {
            s.insert(Node(l,l+c[i]-1,i));
            l+=c[i]; c[i]=0;
        }
}
inline int query(const int& l,const int& r,const int& v) {
    IT itr=split(r+1),itl=split(l); int s=0;
    for (;itl!=itr;++itl) if (itl->v==v) s+=itl->r-itl->l+1;
    return s;
}
inline void print() {
    std::cout<<"s:\n";
    for (register IT it=s.begin();it!=s.end();++it)
        std::cout<<it->l<<' '<<it->r<<' '<<it->v<<'\n';
    std::cout<<"end\n";
}
int main() {
    std::cin>>n>>m;
    for (register int i=1;i<=n;++i) s.insert(Node(i,i,read_char()));
    for (;m;--m) {
        std::cin>>opt>>l>>r;
        if (opt==1) std::cout<<query(l,r,read_char())<<'\n';
        else if (opt==2) assign(l,r,read_char());
        else sort(l,r);
//      print();
    }
}