代码

#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
namespace io{
	const int BUFSIZE = 1 << 20;
	char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;
	char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE;
	inline char getch(){
		if(is == it)
			it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
		return (is == it) ? EOF : *is++;
	}
	inline int getint(){
		int res = 0; bool neg = false; char ch = getch();
		while(!(isdigit(ch) or ch == '-') and ch != EOF)
			ch = getch();
		if(ch == '-')
			neg = true, ch = getch();
		while(isdigit(ch))
			res = res * 10 + (ch - '0'), ch = getch();
		return neg ? -res : res;
	}
	inline double getreal(){
		double res = 0, base; bool neg = false; char ch = getch();
		while(!(isdigit(ch) or ch == '-') and ch != EOF)
			ch = getch();
		if(ch == '-')
			neg = true, ch = getch();
		while(isdigit(ch))
			res = res * 10.0 + (ch - '0'), ch = getch();
		if(ch == '.'){
			base = 0.1;
			ch = getch();
			while(isdigit(ch))
				res += (ch - '0') * base, base *= 0.1, ch = getch();
		}
		return neg ? -res : res;
	}
	inline void flush(){
		fwrite(obuf, 1, os - obuf, stdout);
		os = obuf;
	}
	inline void putch(char ch){
		*os++ = ch;
		if(os == ot)
			flush();
	}
	inline void putint(int res){
		char q[10]; int top;
		if(res < 0)
			putch('-'), res = -res;
		if(res == 0)
			putch('0');			
		top = 0;
		while(res)
			q[top++] = res % 10 + '0', res /= 10;
		while(top--)
			putch(q[top]) ;
	}
	inline void putreal(double res, int acc = 0){
		int who; double tmp, base = 1.0;
		if(res < 0)
			putch('-'), res = -res;	
		tmp = res - (int)(res);
		for(register int i = 1; i <= acc + 1; ++i)
			base /= 10.0, who = tmp / base, tmp -= who * base;
		if(who >= 5)
			res += base * 10.0;
		base = 1.0;
		while(res / base >= 10.0)
			base *= 10.0;
		while(base >= 1.0)
			who = res / base, putch(who + '0'), res -= who * base, base /= 10.0;
		if(acc){
			putch('.');
			base = 0.1;
			while(acc--)
				who = res / base, putch(who + '0'), res -= who * base, base /= 10.0;
		}
	}
}
const uint MaxN=200000,MaxK=50,Mod=998244353;
uint n,m;
struct Node{
	uint tag;
	uint prt,ch[7];
}trie[MaxN*MaxK*2+1];
uint trieSize=0;
#define NewNode() (++trieSize)
#define GetCh(u,p)\
(trie[u].ch[p]?trie[u].ch[p]:(trie[trie[u].ch[p]=++trieSize].prt=u,trieSize))
struct Worm{
	uint len,prev,next;
	uint deep,tRoot,p;
}a[MaxN+1];
char s[uint(1e7)+1];
inline void Solve(){
	n=io::getint(),m=io::getint();
	for(uint i=1;i<=n;i++){
		a[i].len=io::getint();
		a[i].deep=1;
		a[i].tRoot=GetCh(0,a[i].len);
		a[i].p=i;
		trie[a[i].tRoot].tag++;
	}
	uint op,k,x,y,dis;
	for(uint i=1;i<=m;i++){
		op=io::getint();
		if(op==1){
			x=io::getint(),y=io::getint();
			a[x].next=y;
			a[y].prev=x;
			for(uint now=x;a[now].deep<MaxK&&now;now=a[now].prev){
				while(a[now].deep<MaxK&&a[a[now].p].next){
					a[now].p=a[a[now].p].next;
					a[now].deep++;
					a[now].tRoot=GetCh(a[now].tRoot,a[a[now].p].len);
					trie[a[now].tRoot].tag++;
				}
			}
		}else if(op==2){
			dis=0;
			x=io::getint();
			for(uint now=x;dis<MaxK&&now;now=a[now].prev){
				while(a[now].p!=x){
					a[now].p=a[a[now].p].prev;
					a[now].deep--;
					trie[a[now].tRoot].tag--;
					a[now].tRoot=trie[a[now].tRoot].prt;
				}
				dis++;
			}
			a[a[x].next].prev=0;
			a[x].next=0;
		}else{
			uint siz=0;
			s[siz]=io::getch();
			while('0'<=s[siz]&&s[siz]<='9')s[++siz]=io::getch();
			k=io::getint();
			long long ans=1;
			for(uint i=0;i<siz-k+1;i++){
				uint now=0;
				for(uint j=i;j<i+k;j++){
					if(!trie[now].ch[s[j]-'0']){
						ans=0;
						break;
					}
					now=trie[now].ch[s[j]-'0'];
				}
				if(!ans)break;
				ans=ans*trie[now].tag%Mod;
			}
			cout<<ans<<'\n';
		}
	}
}
int main(){
//	cout<<sizeof(trie)/1000/1000;
//	freopen("earthworm.in","r",stdin);
//	freopen("earthworm.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
//	int T;
//	cin>>T;
//	while(T--)
		Solve();
	return 0;
}

评测结果