题解【语文1（chin1）- 理理思维】

link

喵~珂朵莉树AC

珂朵莉树？见此处~

这数据结构太暴力了，所以不讲了

Code:

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#include<set>
#include<cctype>
#include<cstring>
using namespace std ;
inline void read(int &x) {
    char ch=getchar();
    int s=0,f=1;
    while (!(ch>='0'&&ch<='9')) {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    x=s*f;
}
#define ITer  set<node>::iterator
namespace odt{
	struct node{
		mutable char v ;
		int l , r ;
		node(int Ll,int Rr=-1,char Vv=0): l(Ll) , r(Rr) , v(Vv){}
		bool operator < (node n)const{
			return l<n.l ;
		}
	} ; 
	set<node> s ;
	ITer split(int pos){
		ITer it = s.lower_bound(node(pos)) ;
		if(it!=s.end() && it->l == pos) return it ;
		--it ; int L = it->l , R = it->r ; char V = it->v ;
		s.erase(it) ;
		s.insert(node(L,pos-1,V)) ;
		return s.insert(node(pos,R,V)).first ;
	}
	void assign_val(int x,int y,char val=0){
		val = tolower(val) ; 
		ITer yv = split(y+1) , xv = split(x) ;
		s.erase(xv,yv) ;
		s.insert(node(x,y,val)) ;
	}
	int query(int x,int y,char k){
		k = tolower(k) ;
		int ans = 0 ;
		ITer yv = split(y+1) , xv = split(x) ;
		for(;xv!=yv;++xv) if(xv->v==k) ans+=xv->r-xv->l+1 ;
		return ans ;
	}
	void st(int x,int y){
		int ton[257] ;
		memset(ton,0,sizeof(ton)) ;
		ITer yv = split(y+1) , xv = split(x) ;
		ITer it = xv ;
		for(;xv!=yv;++xv) ton[xv->v] += xv->r-xv->l+1;
		s.erase(it,yv) ;
		for(int i=0;i<='z';++i)
			if(ton[i])
				s.insert(node(x,x+ton[i]-1,i)) , x+=ton[i] ;
	}
	void print(){
		ITer x = s.begin() ;
		for(;x!=s.end();++x){
			cerr<<"pair<"<<x->l<<","<<x->r<<","<<x->v<<"> ;"<<endl ;
		}
	}
};
int n,m ; string ipt ;
int nl = 0 ;
pair<int,char> pr ;
int main(){
	char last ;
	read(n) , read(m) ; cin>>ipt ;
	for(auto& i:ipt) i = tolower(i) ;
	last = ipt[0] ; pr = make_pair(0,ipt[0]) ;
	for(int i=0,len=ipt.size();i<=len;++i){
		if(ipt[i]==last) ++pr.first ;
		else{
			odt::s.insert(odt::node(nl,nl+pr.first-1,pr.second)) ;
			nl += pr.first ; pr = make_pair(1,ipt[i]) ; last = ipt[i] ;
		}
	}
	odt::print() ;
	while(m--){
		int opt,x,y; char k ;
		read(opt) ;
		switch(opt){
			case 1: { read(x),read(y),scanf("%c",&k),k=tolower(k),--x,--y,printf("%d
",odt::query(x,y,k)) ; break ; }
			case 2: { read(x),read(y),scanf("%c",&k),k=tolower(k),--x,--y,odt::assign_val(x,y,k) ; break ; }
			case 3: { read(x),read(y),--x,--y,odt::st(x,y) ; break ; }
		}
	}
}

98行切紫题，爽！