```cpp
#include<cstdio>
#include<cctype>
using namespace std;
const int N=5e4+5,M=26;
int n,q,sum[M][N*4],tag[M][N*4],h[N*4],b[M];
int read(){
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return x;
}
int readc(){
char k;
while(!isalpha(k=getchar()));
return isupper(k)?k-65:k-97;
}
void pushup(int x,int i){
sum[i][x]=sum[i][x*2]+sum[i][x*2+1];
}
void change(int i,int x,int k){
sum[i][x]=k*h[x],tag[i][x]=k;
}
void pushdown(int x,int i){
if(~tag[i][x]){
change(i,x*2,tag[i][x]);
change(i,x*2+1,tag[i][x]);
tag[i][x]=-1;
}
}
void build(int x,int l,int r){
for(int i=0;i<M;++i) tag[i][x]=-1;
h[x]=r-l+1;
if(l==r){
sum[readc()][x]=1;
return;
}
int mid=l+r>>1;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
for(int i=0;i<M;++i) pushup(x,i);
}
void modify(int x,int l,int r,int L,int R,int id,int k){
if(tag[id][x]==k) return;
if(l>=L&&r<=R) return change(id,x,k);
pushdown(x,id);
int mid=l+r>>1;
if(L<=mid) modify(x*2,l,mid,L,R,id,k);
if(R>mid) modify(x*2+1,mid+1,r,L,R,id,k);
pushup(x,id);
}
void work(int l,int r,int id){
for(int i=0;i<M;++i) modify(1,1,n,l,r,i,i==id);
}
int query(int x,int l,int r,int L,int R,int id){
if(!sum[id][x]) return 0;
if(l>=L&&r<=R) return sum[id][x];
pushdown(x,id);
int mid=l+r>>1,ans=0;
if(L<=mid) ans=query(x*2,l,mid,L,R,id);
if(R>mid) ans+=query(x*2+1,mid+1,r,L,R,id);
return ans;
}
int main(){
n=read(),q=read();
build(1,1,n);
for(int op,x,y;q--;){
op=read(),x=read(),y=read();
switch(op){
case 1:printf("%d\n",query(1,1,n,x,y,readc()));break;
case 2:work(x,y,readc());break;
case 3:{
for(int i=0;i<M;++i) b[i]=query(1,1,n,x,y,i);
for(int i=0;i<M;x+=b[i++]) if(b[i]) work(x,x+b[i]-1,i);
}
}
}
return 0;
}
```
by StarLbright40 @ 2021-09-26 20:48:10
就那个二维数组,建议开成结构体。
当一个二维数组很大的时候好像访问元素特别慢(你可以尝试交换二维数组的两个维度等),好像是涉及到 CPU 的分支预判什么的。。
by KCID @ 2021-09-26 20:51:33
不是我说你二维数组这样开就是出大问题,你看看你的内存访问咋访问的
by Qiuly @ 2021-09-26 20:53:07
你这个内存访问不是巨大不连续
by Qiuly @ 2021-09-26 20:53:22
@[Qiuly](/user/113190) 我觉得 QiuQiu 说的很有道理。 /se
by MuYC @ 2021-09-26 20:57:07
orz 龙
by Qiuly @ 2021-09-26 20:57:31
@[Qiuly](/user/113190) 我感觉 @ 或者不 @ Qiu 都是一样的,除非 Qiu 把通知直接点掉()
by MuYC @ 2021-09-26 21:00:38
确实
by Qiuly @ 2021-09-26 21:04:08
@[Qiuly](/user/113190) 可以具体说说是怎么不连续的吗,不是很了解这块,谢谢~~只知道先行后列比先列后行快~~
by StarLbright40 @ 2021-09-26 21:09:34
@[星光0000](/user/128570) 就我觉得啊,你慢的主要原因就是你的存储结构是上面这种:
![](https://cdn.luogu.com.cn/upload/image_hosting/rh2ioeev.png)
但是结构体的信息则是下面这种,当你需要查询某个信息的时候,你需要跳老远去找对应的数组,而结构体就只用查相邻的地方,这估计是区别吧()。
by MuYC @ 2021-09-26 21:21:50