1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
int n, m, a[200005], pre[200005], nxt[200005], opt, uu, vv, k;
ull mii[55], g[105], f[105];
char ss[10000005];
const int mod=998244353, orz=19260817;
const ull bse=131;
struct HashTable{
int cnt, hea[19260825];
struct Edge{
ull x; int y, nxt;
}edge[19260825];
void upd(ull x, int v){
int p=x%orz;
for(int i=hea[p]; i; i=edge[i].nxt){
if(edge[i].x==x){
edge[i].y = (edge[i].y + v + mod) % mod;
return ;
}
}
edge[++cnt].nxt = hea[p];
edge[cnt].x = x;
edge[cnt].y = v;
hea[p] = cnt;
}
int query(ull x){
int p=x%orz, re=0;
for(int i=hea[p]; i; i=edge[i].nxt)
if(edge[i].x==x){
re = edge[i].y;
break;
}
return re;
}
}hst;
void rn(int &x){
x = 0;
char ch=getchar();
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0' && ch<='9'){
x = x * 10 + ch - '0';
ch = getchar();
}
}
int main(){
rn(n); rn(m);
mii[0] = 1;
for(int i=1; i<=50; i++)
mii[i] = mii[i-1] * bse;
for(int i=1; i<=n; i++){
rn(a[i]);
hst.upd(a[i], 1);
}
while(m--){
rn(opt);
if(opt==1){
rn(uu); rn(vv);
int l=50, r=49;
for(int i=uu; i && l>1; i=pre[i])
f[--l] = a[i];
for(int i=vv; i && r<=100; i=nxt[i])
f[++r] = a[i];
for(int i=1; i<=r; i++)
g[i] = g[i-1] * bse + f[i];
for(int i=l; i<=49; i++)
for(int j=50; j<=r && j-i+1<=50; j++)
hst.upd(g[j]-g[i-1]*mii[j-i+1], 1);
nxt[uu] = vv; pre[vv] = uu;
}
if(opt==2){
rn(uu); vv = nxt[uu];
int l=50, r=49;
for(int i=uu; i && l>1; i=pre[i])
f[--l] = a[i];
for(int i=vv; i && r<=100; i=nxt[i])
f[++r] = a[i];
for(int i=1; i<=r; i++)
g[i] = g[i-1] * bse + f[i];
for(int i=l; i<=49; i++)
for(int j=50; j<=r && j-i+1<=50; j++)
hst.upd(g[j]-g[i-1]*mii[j-i+1], -1);
nxt[uu] = 0; pre[vv] = 0;
}
if(opt==3){
scanf("%s", ss+1);
rn(k);
int l=strlen(ss+1), ans=1;
ull tmp=0;
for(int i=1; i<=l; i++){
tmp = tmp * bse + ss[i] - '0';
if(i>k) tmp -= mii[k] * (ss[i-k] - '0');
if(i>=k) ans = (ull)hst.query(tmp) * ans % mod;
}
printf("%d\n", ans);
}
}
return 0;
}
|