代码

#include<cstdio>
#define re register
#define ull unsigned long long
using namespace std;
const int Mxdt=1000000;	//单次大小 
inline char gc(){
	static char buf[Mxdt],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline char pc(char ch,bool bj){
	static char buf[Mxdt],*p1=buf,*p2=buf+Mxdt;
	return (bj||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0;
}
void print(int x)
{
	if(x>9)print(x/10);
	pc(x%10^48,false);
}
inline void printnum(int x,char ch)
{
	print(x),pc(ch,false);
}
inline int read(){
	re int t=0;re char v=gc();
	while(v<'0')v=gc();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
	return t;
}
int nxt[20000002],cnt,val[20000002];
ull to[20000002],pw[52],B=131;
struct hashtable{
	int head[65536];
	inline void ins(re ull x,re int y){
		re int tmp=x&65535;
		for(re int i=head[tmp];i;i=nxt[i])if(to[i]==x){val[i]+=y;return;}
		to[++cnt]=x,nxt[cnt]=head[tmp],head[tmp]=cnt,val[cnt]=y;
	}
	inline int ask(re ull x){
		re int tmp=x&65535;
		for(re int i=head[tmp];i;i=nxt[i])if(to[i]==x)return val[i];
		return 0;
	}
}H[52];
int n,L[500002],R[500002],m,l,a[500002],k;
char s[10000002];
const int M=998244353;
int main(){
	n=read(),m=read();
	for(re int i=pw[0]=1;i<=n;++i)pw[i]=pw[i-1]*B;
	for(re int i=1;i<=n;++i)a[i]=read(),H[1].ins(a[i],1);
	while(m--){
		re int o=read();
		if(o==3){
			l=0;
			while(s[l]^' ')s[++l]=gc();
			k=read(),--l;
			re ull hsh=0;
			for(re int i=1;i<=k;++i)hsh=hsh*B+s[i]-'0';
			re int ans=H[k].ask(hsh);
			for(re int i=k+1;i<=l;++i)hsh=hsh*B+s[i]-'0',hsh-=pw[k]*(s[i-k]-'0'),ans=1ll*ans*H[k].ask(hsh)%M;
			printnum(ans,'\n');
		}
		else if(o==2){
			re int x=R[read()];
			for(re int s=L[x],t=1;s&&t<=50;++t,s=L[s]){
				re ull hsh=0;
				for(re int y=s,c=1;c<=50&&y;++c,y=R[y]){hsh=hsh*B+a[y];if(c>t)H[c].ins(hsh,-1);}
			}
			R[L[x]]=0,L[x]=0;
		}
		else{
			re int x=read(),y=read();
			R[x]=y,L[y]=x;
			for(re int s=x,t=1;s&&t<=50;++t,s=L[s]){
				re ull hsh=0;
				for(re int y=s,c=1;c<=50&&y;++c,y=R[y]){hsh=hsh*B+a[y];if(c>t)H[c].ins(hsh,1);}
			}
		}
	}
	pc('o',1);
}

评测结果