我怕不是在做noip题……
注意到$k\le 50$，询问会涉及到的向后$k$数字串个数为$\mathcal O(nk)$，可以考虑直接把所有这些串的hash值存到hash表里面，进行修改操作的时候受影响的串只有$\mathcal O(k^2)$个，暴力维护即可.
卡常死活卡不过去，profile了一发，发现性能瓶颈是unordered_map，改成手写hash表直接3.4s->0.7s. 以后能手写的时候还是手写吧.
代码：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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
using namespace std;
namespace io{
const ele size=1<<20;
char buf[size],*s=buf,*t=buf;
inline char gc(){
return s==t && ((t=(s=buf)+fread(buf,1,size,stdin)),s==t)?EOF:*s++;
}
template<class I>inline void gi(I&a){
char c;
while ((c=gc())<'0' || c>'9');
a=c-'0';
while ((c=gc())>='0' && c<='9') a=(a<<3)+(a<<1)+c-'0';
}
inline void gs(char *s){
char c;
while ((c=gc())<'0' || c>'9');
*s++=c;
while ((c=gc())>='0' && c<='9') *s++=c;
*s=0;
}
char obuf[size],*os=obuf,*ot=obuf;
inline bool flush(){
fwrite(obuf,1,ot-os,stdout);
os=ot=obuf;
return true;
}
inline void pc(char c){
ot==obuf+size && flush(),*ot++=c;
}
template<class I>inline void pi(I x){
if (!x) pc('0');
else{
char s[20],cnt=0;
while (x) s[cnt++]=x%10+'0',x/=10;
while (cnt) pc(s[--cnt]);
}
}
}
using io::gc;
using io::gi;
using io::gs;
using io::pc;
using io::pi;
struct hashmap{
const static ele R=8000009;
ll a[R];
ele b[R];
bool c[R];
hashmap(){ memset(c,0,sizeof(c)); }
inline ele find(ll x){
ele i=x%R;
for (; c[i] && a[i]!=x; (i+=1)%=R);
!c[i] && (c[i]=true,a[i]=x,b[i]=0);
return i;
}
inline ele& operator[](ll i){
return b[find(i)];
}
};
const ll seed=233;
const ll p[]={29,30};
const ll P[]={(1<<p[0])-1,(1<<p[1])-1};
ele n,m,K,a[maxn],prv[maxn],nxt[maxn];
char s[maxL];
ll h[2][maxL],xl[2][55];
hashmap mp;
template<class I>inline I _mod(I x,ele i){
return (x=(x>>p[i])+(x&P[i]))>=P[i]?x-P[i]:x;
}
inline void upd(ele u,ele v,ele delta){
ll t1=0,t2=0;
for (int i=1; i<=K && ~u; ++i,u=prv[u]){
t1*=seed; t1+=a[u]; t1=_mod(t1,0);
t2*=seed; t2+=a[u]; t2=_mod(t2,1);
ll t3=t1,t4=t2;
ele w=v;
for (int j=1; i+j<=K && ~w; ++j,w=nxt[w]){
t3+=xl[0][i+j-1]*a[w]; t3=_mod(t3,0);
t4+=xl[1][i+j-1]*a[w]; t4=_mod(t4,1);
mp[t3+(t4<<30)]+=delta;
}
}
}
int main(){
gi(n); gi(m);
K=m>300000?1:50;
for (int i=0; i<n; ++i) gi(a[i]),++mp[(ll)a[i]+((ll)a[i]<<30)];
for (int j=0; j<2; ++j){
xl[j][0]=1;
for (int i=1; i<=K; ++i) xl[j][i]=_mod(xl[j][i-1]*seed,j);
}
memset(prv,-1,sizeof(prv));
memset(nxt,-1,sizeof(nxt));
while (m--){
ele op,u,v;
gi(op);
if (op==1){
gi(u); gi(v); --u,--v;
nxt[u]=v; prv[v]=u;
upd(u,v,1);
}
else if (op==2){
gi(u); --u; v=nxt[u];
nxt[u]=prv[v]=-1;
upd(u,v,-1);
}
else{
gs(s); gi(u);
ele L=strlen(s);
for (int j=0; j<2; ++j){
h[j][L]=0;
for (int i=L-1; ~i; --i) h[j][i]=_mod(h[j][i+1]*seed+s[i]-'0',j);
}
ele ans=1;
for (int i=0; i+u<=L; ++i){
ll t1=_mod(h[0][i]+P[0]*P[0]-h[0][i+u]*xl[0][u],0);
ll t2=_mod(h[1][i]+P[1]*P[1]-h[1][i+u]*xl[1][u],1);
ll tmp=t1+(t2<<30);
ans=(ll)ans*mp[tmp]%MOD;
}
pi(ans);
pc('\n');
}
}
io::flush();
return 0;
}