- 想要使用珂朵莉树帮HansBug理理思维
- 结果:记录
- 然后调了一下午,试图把HansBug的思维理清(
- 排序用的是桶排。
- 问题大概查出来了,是
msort
出了锅,但是没发现哪里错了....../kk/kk
- 请大家来帮帮忙,一起来理理HansBug的思维吧(
- 这里是代码:
#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>
#include<cctype>
#include<iostream>
#include<cstring>
#define MAXN 50005
using namespace std;
struct Node{
int l,r;
mutable int val;
Node(int L,int R,int V)
:l(L),r(R),val(V){}
Node(int L)
:l(L){}
bool operator<(const Node &o)const{
return l<o.l;
}
};
int f(char ch){
if(ch>='a'&&ch<='z')return ch-'a';
return ch-'A';
}
set<Node>s;
int n,m;
#define Sit set<Node>::iterator
Sit split(int pos){
Sit it=s.lower_bound(Node(pos));
if(it!=s.end()&&it->l==pos){
return it;
}
it--;
int L=it->l,R=it->r,V=it->val;
s.erase(it);
s.insert(Node(L,pos-1,V));
return s.insert(Node(pos,R,V)).first;
}
void assign(int l,int r,int k){
Sit itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(Node(l,r,k));
}
int Query(int l,int r,int k){
int ans=0;
Sit itr=split(r+1),itl=split(l);
for(Sit it=itl;it!=itr;it++){
if(it->val==k){
ans+=it->r-it->l+1;
}
}
return ans;
}
int B[300];
void msort(int l,int r){
memset(B,0,sizeof(B));
Sit itr=split(r+1),itl=split(l);
for(Sit it=itl;it!=itr;it++){
B[it->val]+=it->r-it->l+1;
s.erase(it);
}
int k=l;
for(int i=0;i<26;i++){
if(B[i]){
s.insert(Node(k,k+B[i]-1,i));
k+=B[i];
}
}
}
string ch;
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
cin>>ch;
for(int i=0;i<n;i++){
s.insert(Node(i+1,i+1,f(ch[i])));
}
while(m--){
int opt,l,r;
char CH;
cin>>opt;
if(opt==1){
cin>>l>>r>>CH;
cout<<Query(l,r,f(CH))<<'\n';
}
else if(opt==2){
cin>>l>>r>>CH;
assign(l,r,f(CH));
}
else{
cin>>l>>r;
msort(l,r);
}
}
return 0;
}