代码

#include <bits/stdc++.h>
#define Pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline int R()
{
	int rt = 0; char ch = getchar(); bool isn = 0;
	for ( ; ch < '0' || ch > '9'; ch = getchar() ) isn = ch == '-' ? 1 : isn;
	for ( ; ch >= '0' && ch <= '9'; ch = getchar() ) rt = rt * 10 + ch - '0';
	return isn ? -rt : rt;
}
const int Mod = 998244353, MAXN = 2e5 + 7, MAXS = 1e7 + 7;
const ull Hmod = 70000007, Hbs = 73;
struct T
{
	ull val; int cnt;
	T ( ull nv = 0, int nc = 0 ) { val = nv, cnt = nc; }
}t[MAXN * 50 * 2];
int nu;

struct E
{
	int to, nxt;
}o[MAXN * 50 * 2];
int nue;

struct N
{
	int fe;
}a[Hmod + 7];

void Ins ( ull val, int nc )
{
	ull nf = val % Hmod;
	for ( int ne = a[nf].fe; ne; ne = o[ne].nxt )
	{
		int to = o[ne].to;
		if ( t[to].val == val ) { t[to].cnt += nc; return; }
	}
	t[++nu].val = val, t[nu].cnt = 1;
	o[++nue].to = nu, o[nue].nxt = a[nf].fe, a[nf].fe = nue;
}

ll Hquery ( ull val )
{
	ull nf = val % Hmod;
	for ( int ne = a[nf].fe; ne; ne = o[ne].nxt )
	{
		int to = o[ne].to;
		if ( t[to].val == val ) return t[to].cnt;
	}
	return 0;
}

struct L
{
	int pre, nxt, num;
}l[MAXN];

void Merge ( int nl, int nr )
{
	l[nl].nxt = nr, l[nr].pre = nl;
	for ( int i = nl, lcnt = 1; lcnt < 50 && i; i = l[i].pre, ++lcnt )
	{
		int sp = l[i].nxt, len = 2;
		ull val = l[i].num;
		for ( ; sp != nr; sp = l[sp].nxt, ++len ) val = val * Hbs + l[sp].num;
		for ( ; sp && len <= 50; sp = l[sp].nxt, ++len ) val = val * Hbs + l[sp].num, Ins ( val, 1 );
	}
}

void Split ( int nl )
{
	int nr = l[nl].nxt;
	for ( int i = nl, lcnt = 1; lcnt < 50 && i; i = l[i].pre, ++lcnt )
	{
		int sp = l[i].nxt, len = 2;
		ull val = l[i].num;
		for ( ; sp != nr; sp = l[sp].nxt, ++len ) val = val * Hbs + l[sp].num;
		for ( ; sp && len <= 50; sp = l[sp].nxt, ++len ) val = val * Hbs + l[sp].num, Ins ( val, -1 );
	}
	l[nl].nxt = 0, l[nr].pre = 0;
}

int n, m;
char s[MAXS];
ull hs[MAXS], pn[MAXS];
ull Ghs ( int l, int r ) { return hs[r] - hs[l - 1] * pn[r - l + 1]; }

ll Query ( int k )
{
	int nl = strlen ( s + 1 );
	ll rt = 1;
	for ( int i = 1; i <= nl; ++i ) hs[i] = hs[i - 1] * Hbs + s[i] - '0' + 1;
	for ( int i = 1; i + k - 1 <= nl; ++i ) { rt = rt * Hquery ( Ghs ( i, i + k - 1 ) ) % Mod; if ( !rt ) return 0; }
	return rt;
}

int main()
{
//	freopen ( "test.in", "r", stdin );
//	cerr << ( sizeof t + sizeof o + sizeof a ) / ( 1 << 20 ) << endl;
	n = R(), m = R();
	for ( int i = 1; i <= n; ++i ) l[i].num = R() + 1, Ins ( l[i].num, 1 );
	pn[0] = 1;
	for ( int i = 1; i <= 10000000; ++i ) pn[i] = pn[i - 1] * Hbs;
	for ( ; m; --m )
	{
		int tp = R();
		if ( tp == 1 )
		{
			int x = R(), y = R();
			Merge ( x, y );
			continue;
		}
		if ( tp == 2 ) { Split ( R() ); continue; }
		if ( tp == 3 )
		{
			scanf ( "%s", s + 1 );
			printf ( "%lld\n", Query ( R() ) );
			continue;
		}
	}
	return 0;
}

评测结果