代码

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

const int ioSize = 1 << 21 | 1;
char iBuf[ioSize], *iS, *iE, oBuf[ioSize], *oS(oBuf), *oE(oBuf + ioSize);
inline char getc() { return iS == iE ? iE = iBuf + fread(iS = iBuf, 1, ioSize, stdin), iS == iE ? EOF : *iS++ : *iS++; }
void readi(int &x)
{
	char c;
	for (c = getc(); !isdigit(c); c = getc())
		;
	x = c ^ '0';
	for (c = getc(); isdigit(c); c = getc())
		(x *= 10) += c ^ '0';
}
void reads(char *s)
{
	char c;
	for (c = getc(); !isdigit(c); c = getc())
		;
	*s++ = c;
	for (c = getc(); isdigit(c); c = getc())
		*s++ = c;
	*s = '\0';
}
inline void flush()
{
	fwrite(oBuf, 1, oS - oBuf, stdout);
	oS = oBuf;
}
inline void putc(char c)
{
	*oS++ = c;
	if (oS == oE)
		flush();
}
void puti(int x)
{
	char qu[20], *qr = qu;

	do
		*qr++ = x % 10 ^ '0';
	while (x /= 10);

	while (qr != qu)
		putc(*--qr);
	putc('\n');
}

typedef unsigned long long ull;
typedef unsigned int uint;
const int maxN = 200005, maxK = 50, maxL = 10000005;
const uint mod = 100057, base = 31;
const int Mod = 998244353;

int N, M, A[maxN];
int Pre[maxN], Next[maxN];
ull Pow1[maxN];
int Pow2[maxN];
char S[maxL];

ull Key[maxN * maxK + 1];
int Val[maxN * maxK + 1], _Next[maxN * maxK + 1], tot;

struct hashtable
{
	int Head[mod];
	void insert(ull v, uint t)
	{
		for (int i = Head[t]; i; i = _Next[i])
			if (Key[i] == v)
			{
				++Val[i];
				return;
			}
		++tot;
		Key[tot] = v, Val[tot] = 1, _Next[tot] = Head[t];
		Head[t] = tot;
	}
	void erase(ull v, uint t)
	{
		for (int i = Head[t]; i; i = _Next[i])
			if (Key[i] == v)
			{
				--Val[i];
				return;
			}
	}
	int query(ull v, uint t)
	{
		for (int i = Head[t]; i; i = _Next[i])
			if (Key[i] == v)
				return Val[i];
		return 0;
	}
} Hash[maxK + 1];

int main()
{
	readi(N), readi(M);
	for (int i = 1; i <= N; ++i)
	{
		readi(A[i]);
		Hash[1].insert(A[i], A[i]);
	}

	Pow1[0] = 1;
	for (int i = 1; i <= N; ++i)
		Pow1[i] = Pow1[i - 1] * base;
	Pow2[0] = 1;
	for (int i = 1; i <= N; ++i)
		Pow2[i] = Pow2[i - 1] * base % mod;

	for (int o, i, j, k; M--;)
	{
		readi(o);
		static int buffer1[maxK + 1], buffer2[maxK + 1];
		static ull h1[maxK + 1];
		static uint h2[maxK + 1];
		int cnt1 = 0, cnt2 = 0;
		if (o == 1)
		{
			readi(i), readi(j);
			for (int x = i; x && cnt1 < maxK; x = Pre[x])
				buffer1[++cnt1] = A[x];
			for (int x = j; x && cnt2 < maxK; x = Next[x])
				buffer2[++cnt2] = A[x];
			for (int x = 1; x <= cnt1; ++x)
			{
				h1[x] = h1[x - 1] + buffer1[x] * Pow1[x - 1];
				h2[x] = (h2[x - 1] + buffer1[x] * Pow2[x - 1]) % mod;
			}
			ull hash1 = 0;
			uint hash2 = 0;
			for (int x = 1; x <= cnt2; ++x)
			{
				hash1 = hash1 * base + buffer2[x];
				hash2 = (hash2 * base + buffer2[x]) % mod;
				for (int y = 1; y <= cnt1 && x + y <= maxK; ++y)
				{
					ull t1 = h1[y] * Pow1[x] + hash1;
					uint t2 = ((ull)h2[y] * Pow2[x] + hash2) % mod;
					Hash[x + y].insert(t1, t2);
				}
			}
			Pre[j] = i, Next[i] = j;
		}
		else if (o == 2)
		{
			readi(i);
			for (int x = i; x && cnt1 < maxK; x = Pre[x])
				buffer1[++cnt1] = A[x];
			for (int x = Next[i]; x && cnt2 < maxK; x = Next[x])
				buffer2[++cnt2] = A[x];
			for (int x = 1; x <= cnt1; ++x)
			{
				h1[x] = h1[x - 1] + buffer1[x] * Pow1[x - 1];
				h2[x] = (h2[x - 1] + buffer1[x] * Pow2[x - 1]) % mod;
			}
			ull hash1 = 0;
			uint hash2 = 0;
			for (int x = 1; x <= cnt2; ++x)
			{
				hash1 = hash1 * base + buffer2[x];
				hash2 = (hash2 * base + buffer2[x]) % mod;
				for (int y = 1; y <= cnt1 && x + y <= maxK; ++y)
				{
					ull t1 = h1[y] * Pow1[x] + hash1;
					uint t2 = ((ull)h2[y] * Pow2[x] + hash2) % mod;
					Hash[x + y].erase(t1, t2);
				}
			}
			Pre[Next[i]] = 0;
			Next[i] = 0;
		}
		else
		{
			reads(S + 1), readi(k);
			ull hash1 = 0;
			uint hash2 = 0;
			int ans = 1;
			for (i = 1; i < k; ++i)
			{
				hash1 = hash1 * base + (S[i] ^ '0');
				hash2 = (hash2 * base + (S[i] ^ '0')) % mod;
			}
			for (i = k; S[i] && ans; ++i)
			{
				hash1 = hash1 * base + (S[i] ^ '0');
				hash2 = (hash2 * base + (S[i] ^ '0')) % mod;
				ans = (ull)ans * Hash[k].query(hash1, hash2) % Mod;
				hash1 = hash1 - (S[i - k + 1] ^ '0') * Pow1[k - 1];
				hash2 = (hash2 + mod - (S[i - k + 1] ^ '0') * Pow2[k - 1] % mod) % mod;
			}
			puti(ans);
		}
		// puts("---------------------");
	}

	flush();

	return 0;
}

评测结果