rt .

这是拿 vector 实现的一个块链，按理说应该没有 RE 的情况，各种函数的边界值也是注意了的。但是在实际情况下随着块长 S 的减小，会出现 RE 的情况。

然后就是那个 Search 函数，在调用的时候如果暴力做是没有问题的，但是如果这样写就会导致危险调用。

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=1e6+10;
struct node {
	string s;
	int pre=-1,nex=-1;
	int cnt[30],mach;
};

int n,m,blo;
int qaq;
string p;
int S=3000;
vector<node> e;
inline void rebuild(int loc) {
	int len2=e[loc].s.size(),len1=p.size();
	for (int i=0;i<=len2-len1;i++) e[loc].mach+=(e[loc].s.substr(i,len1)==p);
	return ;
}
inline void del(int loc,int l,int r) {
	for (int i=l;i<=r;i++) e[loc].cnt[e[loc].s[i]-'a']--;
	return ;
}
inline void split(int loc) {
	if (e[loc].s.size()<(S<<1)) return ;
	node tmp=e[loc];
	int nw=++blo;e.push_back(tmp);
	e[nw].pre=loc,e[nw].nex=e[loc].nex;
	e[e[loc].nex].pre=nw;e[loc].nex=nw;
	int len=e[loc].s.size();
	del(loc,S,len-1);
	e[loc].s.erase(S,len-S);
	rebuild(loc);
	del(nw,0,S-1);
	e[nw].s.erase(0,S);
	if (e[nw].s.size()>(S<<1)) split(nw);
	else rebuild(nw);
	return ;
}
inline void add(int loc,string s) {
	for (int i=0;i<s.size();i++) e[loc].cnt[s[i]-'a']++;
	return ;
}
inline void Insert(int x,string s) {
	int loc=0;
	while (x>e[loc].s.size()) {
		x-=e[loc].s.size();
		if (e[loc].nex==-1) {
			e[loc].s+=s;add(loc,s); 
			if (e[loc].s.size()>(S<<1)) split(loc);
			return ;
		}
		loc=e[loc].nex;
	}x--;
	int len=e[loc].s.size();
	string tmp="";
	if (x>0) tmp+=e[loc].s.substr(0,x);
	tmp=tmp+s;
	if (len-x>0) tmp+=e[loc].s.substr(x,len-x);
	e[loc].s=tmp;add(loc,s);
	if (e[loc].s.size()>(S<<1)) split(loc);
	else rebuild(loc);
	return ;
}
inline void Delete(int l,int r) {
	int bll=0;
	while (l>e[bll].s.size()) {
		l-=e[bll].s.size();
		bll=e[bll].nex;
	}l--;
	int blr=0;
	while (r>e[blr].s.size()) {
		r-=e[blr].s.size();
		blr=e[blr].nex;
	}r--;
	if (bll==blr) {
		del(bll,l,r);
		e[bll].s.erase(l,r-l+1);
		rebuild(bll);
		return ;
	}
	else {
		int len=e[bll].s.size();
		del(bll,l,len-1);
		e[bll].s.erase(l,len-l);
		rebuild(bll);
		len=e[blr].s.size();
		del(blr,0,r);
		e[blr].s.erase(0,r+1);
		rebuild(blr);
		for (int it=e[bll].nex;it!=blr and it!=-1;it=e[it].nex) {
			if (e[it].pre!=-1) e[e[it].pre].nex=e[it].nex;
			if (e[it].nex!=-1) e[e[it].nex].pre=e[it].pre;
		}
	}
	return ;
}
inline void Replace(int l,int r,string s) {
	Delete(l,r);
	Insert(l,s);
	return ;
}
inline int Count(int l,int r,char c) {
	int bll=0,res=0;
	while (l>e[bll].s.size()) {
		l-=e[bll].s.size();
		bll=e[bll].nex;
	}l--;
	int blr=0;
	while (r>e[blr].s.size()) {
		r-=e[blr].s.size();
		blr=e[blr].nex;
	}r--;
	if (bll==blr) {
		for (int i=l;i<=r;i++) res+=(e[bll].s[i]==c);
		return res;
	}
	for (int i=l;i<e[bll].s.size();i++) res+=(e[bll].s[i]==c);
	for (int i=0;i<=r;i++) res+=(e[blr].s[i]==c);
	for (int it=e[bll].nex;it!=blr and it!=-1;it=e[it].nex) res+=e[it].cnt[c-'a'];
	return res;
}
namespace std {
	int ne[N];
	inline int KMP(string s,string p) {
		int n=s.size(),m=p.size(),res=0; 
		s=" "+s,p=" "+p;
		for (int i=2,j=0;i<=m;i++) {
			while (j and p[i]!=p[j+1]) j=ne[j];
			if (p[i]==p[j+1]) j++;
			ne[i]=j;
		}
		for (int i=1,j=0;i<=n;i++) {
			while (j and s[i]!=p[j+1]) j=ne[j];
			if (s[i]==p[j+1]) j++;
			if (j==m) {
				res++;
				j=ne[j];
			}
		}
		return res;
	}
	inline int Search(int l,int r) {
		int bll=0,res=0;
		while (l>e[bll].s.size()) {
			l-=e[bll].s.size();
			bll=e[bll].nex;
		}l--;
		int blr=0;
		while (r>e[blr].s.size()) {
			r-=e[blr].s.size();
			blr=e[blr].nex;
		}r--;
		if (bll==blr) {
			string s="";
			for (int i=l;i<=r;i++) s=s+e[bll].s[i];
			s=e[bll].s.substr(l,r-l+1);
			return KMP(s,p);
		}
//		string s="";
//		int num=p.size();int len=e[bll].s.size();
//		for (int i=max(l,len-num+1);i<=len-1;i++) {
//			s+=e[bll].s[i];
//		}
//		int st=l,ln=(len-1)-st+1;
//		s=e[bll].s.substr(st,ln);
//		cout<<"matches : "<<s<<" -----------------------"<<endl;
//		for (int it=e[bll].nex;it!=blr;it++) {
//			for (int i=0;i<min(num-1,int(e[it].s.size()));i++) s+=e[it].s[i];
//			cout<<"matches : "<<s<<" -----------------------"<<endl;
//			res+=KMP(s,p);
//			s="";
//			for (int i=max(0,int(e[it].s.size()-num+1));i<=e[it].s.size()-1;i++) {
//				s+=e[it].s[i];
//			}
//			res+=e[it].mach;
//		}
//		for (int i=0;i<=r;i++) {
//			s+=e[blr].s[i];
//		}
//		cout<<"matches : "<<s<<" -----------------------"<<endl;
//		res+=KMP(s,p);
//		return res;
		string s="";int num=p.size();
		vector<int> has;has.clear();
		for (int i=l;i<e[bll].s.size();i++) s+=e[bll].s[i];
		has.push_back(s.size());
		for (int it=e[bll].nex;it!=blr;it++) s+=e[it].s,res+=e[it].mach,has.push_back(s.size());
		for (int i=0;i<=r;i++) s+=e[blr].s[i];has.push_back(s.size());
		int maxx=s.size();s=" "+s;
		for (int i=0;i<has.size();i++) {
			int v=has[i];
			int l=max(1,v-num+1),r=min(maxx,v+1+num-1);
			int len=r-l+1;
			res+=KMP(s.substr(l,len),p);
		}
		return res;
	}
}
signed main() {
//	freopen("edit.in","r",stdin);
//	freopen("edit.out","w",stdout);
	int _;cin>>_;
	cin>>p;
	e.emplace_back();
	while (_--) {
		string op;int l,r;
		string s;
		cin>>op;
		if (op=="Insert") {
			int pos;
			cin>>pos>>s;pos++;
			if (!qaq) e.back().s=s,add(0,s);
			else Insert(pos,s);
			qaq=1;
		}
		if (op=="Delete") {
			cin>>l>>r;
			Delete(l,r);
		}
		if (op=="Replace") {
			cin>>l>>r>>s;
			Replace(l,r,s);
		}
		if (op=="Count") {
			char c;
			cin>>l>>r>>c;
			cout<<Count(l,r,c)<<endl;
		}
		if (op=="Search") {
			cin>>l>>r;
			cout<<std::Search(l,r)<<endl;
		}
	}
	return (0-0);
}