题意简述
维护字符串，支持以下操作：
- 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();
}
}