【luogu2787】 语文1（chin1）- 理理思维 [线段树]

P2787 语文1（chin1）- 理理思维

P2787 语文1（chin1）- 理理思维

实名哭泣QAQ 我把tg搞错了 调了一下午

因为是将字母对应为(0sim 25)所以无tg不能为(0)应为(-1) 我TM因为这个调了一下午！！！！！！！！！！！！

啊啊啊啊啊啊啊啊啊啊啊啊啊啊

注意本题不区分大小写

排序就将其拆成一个一个的单个区间修改

int chan(char x){return ('a'<=x&&x<='z')?x-'a':x-'A';}
struct node{
	int cnt[26],tg;
	node(){memset(cnt,0,sizeof(cnt));tg=-1;}
}t[N<<2];
node operator + (node x,node y){
    node z;
    for(int i=0;i<26;++i) z.cnt[i]=x.cnt[i]+y.cnt[i];
    return z;
}
void pup(int o){t[o]=t[ls]+t[rs];}
void updnode(int o,int l,int r,int k){
	memset(t[o].cnt,0,sizeof(t[o].cnt));
	t[o].tg=k,t[o].cnt[k]=r-l+1;
}
void pudw(int o,int l,int r){
	if(t[o].tg==-1) return;
	int mid=l+r>>1;
	updnode(ls,l,mid,t[o].tg),updnode(rs,mid+1,r,t[o].tg),t[o].tg=-1;
}
void mdf(int o,int l,int r,int x,int y,int k){
	if(l>y||r<x) return;
	if(x<=l&&r<=y) return updnode(o,l,r,k);
	pudw(o,l,r);int mid=l+r>>1;
	mdf(ls,l,mid,x,y,k),mdf(rs,mid+1,r,x,y,k);
	pup(o);
}
node query(int o,int l,int r,int x,int y){
	if(x<=l&&r<=y) return t[o];
	int mid=l+r>>1;pudw(o,l,r);
	node ret;
	memset(ret.cnt,0,sizeof(ret.cnt));
	if(x<=mid) ret=ret+query(ls,l,mid,x,y);
	if(y>mid) ret=ret+query(rs,mid+1,r,x,y);
	return pup(o),ret;
}
void build(int o,int l,int r){
	if(l==r){t[o].cnt[chan(a[l])]=1;return;}
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pup(o);
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
	rd(n),rd(m),scanf("%s",a+1);
	build(1,1,n);char k;
	for(int i=1,opt,x,y;i<=m;++i){
		rd(opt),rd(x),rd(y);
		if(opt!=3) cin>>k;
		if(opt==1) 
		printf("%d
",query(1,1,n,x,y).cnt[chan(k)]);
		else if(opt==2)	mdf(1,1,n,x,y,chan(k));
		else if(opt==3){
			node ret=query(1,1,n,x,y);
			for(int i=0,r;i<26;++i){if(!ret.cnt[i]) continue;r=x+ret.cnt[i]-1;mdf(1,1,n,x,r,i),x=r+1;			}
		}
/*		for(int i=0;i<26;++i) printf("%d ",t[1].cnt[i]);
		puts("");*/
	}
    return 0;