代码

#include <bits/stdc++.h>

using namespace std;

#define ll 			long long
#define db			double
#define ull			unsigned long long
#define up(i,j,n)		for (int i = j; i <= n; i++)
#define down(i,j,n)	for (int i = j; i >= n; i--)
#define cadd(a,b)		a = add (a, b)
#define cpop(a,b)		a = pop (a, b)
#define cmul(a,b)		a = mul (a, b)
#define pr			pair<int, int>
#define fi			first
#define se			second
#define SZ(x)		(int)x.size()
#define Auto(i,node)	for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int mod = 998244353;
const int MOD = 10002333;

const ull step = 17171717;

const int MAXN = 2e5 + 5;
const int MAXM = 1e7 + 5;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

struct H {
	struct edge {
		int next, v;
		ull q;
	}e[MOD + MOD];
	int LINK[MOD], len;
	inline void ins(int p, ull q, int v){
		e[++len].next = LINK[p]; LINK[p] = len;
		e[len].q = q; e[len].v = v;
	}
	int get(ull x){
		int p = x % MOD;
		Auto (i, p) if (e[i].q == x) return e[i].v;
		return 0;
	}
	void cg(ull x, int v){
		int p = x % MOD;
		Auto (i, p) if (e[i].q == x) return (void) (e[i].v += v);
		ins(p, x, v);
	}
}S;

ull bin[MAXN];

int N, Q;

struct LK {
	int pre, nxt, v;
}a[MAXN];

int pre[MAXN], suf[MAXN];

char s[MAXM];

int main(){
	scanf("%d%d", &N, &Q);
	up (i, 1, N) {
		scanf("%d", &a[i].v);
		S.cg(a[i].v, 1);
	}
	bin[0] = 1;
	up (i, 1, N) bin[i] = bin[i - 1] * step;
	while (Q--) {
		int o, x, y;
		scanf("%d", &o);
		if (o == 1) {
			scanf("%d%d", &x, &y);
			int p = 0, q = 0;
			a[x].nxt = y; a[y].pre = x;
			for (int i = x; i && p < 50; i = a[i].pre) pre[++p] = a[i].v;
			for (int i = y; i && q < 50; i = a[i].nxt) suf[++q] = a[i].v;
			up (i, 1, p) {
				int n = min(q, 50 - i);
				ull cur = 0;
				down (j, i, 1) cur = cur * step + pre[j];
				up (j, 1, n) {
					cur = cur * step + suf[j];
					S.cg(cur, 1);
				}
			}
		} 
		if (o == 2) {
			scanf("%d", &x); y = a[x].nxt;
			int p = 0, q = 0;
			for (int i = x; i && p < 50; i = a[i].pre) pre[++p] = a[i].v;
			for (int i = y; i && q < 50; i = a[i].nxt) suf[++q] = a[i].v;
			up (i, 1, p) {
				int n = min(q, 50 - i);
				ull cur = 0;
				down (j, i, 1) cur = cur * step + pre[j];
				up (j, 1, n) {
					cur = cur * step + suf[j];
					S.cg(cur, -1);
				}
			}
			a[x].nxt = 0; a[y].pre = 0;
		}
		if (o == 3) {
			scanf("%s%d", s + 1, &x); int len = strlen(s + 1);
			ull cur = 0;
			up (i, 1, x - 1) cur = cur * step + (s[i] - '0');
			int ans = 1;
			up (i, x, len) {
				cur = cur * step + (s[i] - '0');
				if (i > x) cur -= bin[x] * (s[i - x] - '0');
				cmul(ans, S.get(cur));
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

评测结果