代码

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=200010,M=10000010;
const ll mod=998244353;
const ull K=1000000007;
int n,m,nxt[N],pre[N],a[N],la,lb,ls; ll ans;
int s[M];
ull sa[M],sb[55],b[55];
namespace HASH {
	const int mod=10000007;
	int hed[mod],cnt=0; struct P { int l,to;ll w;ull s; }; P e[M];
	void Add(int l,ull s,int v) {
		int u=s%(ull)mod;
		for(int i=hed[u];i;i=e[i].to)
			if(e[i].l==l&&e[i].s==s) { e[i].w=(e[i].w+v)%mod;return; }
        e[++cnt]=(P){l,hed[u],v,s},hed[u]=cnt;
    }
    ll Ask(int l,ull s) {
    	int u=s%(ull)mod;
    	for(int i=hed[u];i;i=e[i].to)
    		if(e[i].l==l&&e[i].s==s) return e[i].w;
    	return 0;
	}
};

inline int Max(int x,int y) { return x>y? x:y; }
inline int Min(int x,int y) { return x<y? x:y; }
int read() {
	register int x=0;register char c=getchar();
	for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';x=(x<<1)+(x<<3)+(c^48),c=getchar());
	return x;
}
void reads() {
	register char c=getchar(); for(;c<'1'||c>'6';);
	for(ls=0;c>='1'&&c<='6';s[++ls]=(c^48),c=getchar());
}
void print(ll x) { if(x>9) print(x/10); putchar(x%10+'0'); }
void merge(int x,int y) {
	ull ww;
	la=0; for(int i=x;i&&la<=50;i=pre[i]) sa[++la]=a[i];
	lb=0; for(int i=y;i&&lb<=50;i=nxt[i]) sb[++lb]=a[i];
	for(int i=1;i+i<=la;i++) swap(sa[i],sa[la-i+1]);
	for(int i=1;i<=la;i++) sa[i]=sa[i-1]*K+sa[i];
	for(int i=1;i<=lb;i++) sb[i]=sb[i-1]*K+sb[i];
	for(int l=2;l<=50;l++)
		for(int i=Max(1,l-la),ed=Min(l-1,lb);i<=ed;i++) {
			ww=(sa[la]-sa[la-l+i]*b[l-i])*b[i]+sb[i];
			HASH::Add(l,ww,1);
		}
	nxt[x]=y,pre[y]=x;
}
void split(int x) {
	ull ww;int y=nxt[x];
	la=0; for(int i=x;i&&la<=50;i=pre[i]) sa[++la]=a[i];
	lb=0; for(int i=y;i&&lb<=50;i=nxt[i]) sb[++lb]=a[i];
	for(int i=1;i+i<=la;i++) swap(sa[i],sa[la-i+1]);
	for(int i=1;i<=la;i++) sa[i]=sa[i-1]*K+sa[i];
	for(int i=1;i<=lb;i++) sb[i]=sb[i-1]*K+sb[i];
	for(int l=2;l<=50;l++)
		for(int i=Max(1,l-la),ed=Min(l-1,lb);i<=ed;i++) {
			ww=(sa[la]-sa[la-l+i]*b[l-i])*b[i]+sb[i];
			HASH::Add(l,ww,-1);
		}
	nxt[x]=pre[y]=0;
}
int main() {
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read(),HASH::Add(1,a[i],1);
	b[0]=1; for(int i=1;i<=50;i++) b[i]=b[i-1]*K;
	for(int opt,ta,tb,k;m;--m) {
		opt=read(); if(opt==1) ta=read(),tb=read(),merge(ta,tb);
		else if(opt==2) ta=read(),split(ta);
		else {
			reads(),ans=1,k=read(); ull ww;
			for(int i=1;i<=ls;i++) sa[i]=sa[i-1]*K+(ull)s[i];
			for(int l=1,r;l+k-1<=ls;l++) {
				r=l+k-1,ww=sa[r]-sa[l-1]*b[r-l+1];
				ans=ans*HASH::Ask(k,ww)%mod;
			}
			print(ans),putchar(10);
		}
	}
	return 0;
}

评测结果