发现自己哈希的无数个问题……
首先蚯蚓可以用链表维护这个序列。
然后发现 \(k\) 很少,意味着每次合并或删除所动的子串数量非常少。这启发我们可以把所有出现的长度 \(\le k\) 的子串全部通过哈希塞进一个桶里面,然后查询的时候我们直接再桶中查询。
对于如何维护这个桶,我们可以用一个散列表。
具体一点的操作。对于合并,我们找到第一个队伍靠近尾巴的 \(k\) 个和第二个队伍的靠近头的 \(k\) 个,然后找到所有由两边合并所得到的子串,哈希值丢进散列。
对于删除,我们同样的这样操作,把两边合并得到的子串给从散列中扔出来。也就是合并的逆操作。
对于查询,对于每一个长 \(k\) 的子串,在散列表中查询即可。
分享一个关于我的哈希的故事:我一开始用了一个单模数的哈希,被卡了;然后用了一个双模的,TLE 了;然后发现哈希应该把哈希和长度当成一个 pair 去比较,然后被卡了;然后我换成自然溢出,AC 了。。
实际上这样是正常的。自然溢出比 32 位整型模数的容量大一倍,然后哈希的值存成一个由哈希值和长度组成的 pair 的话也可以大大降低被卡率。至于双模 TLE 的问题,多半是我人傻常熟大 /qd。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef pair<ull,int> pui;
long long read() {
long long res=0, w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {res=res*10+c-48, c=getchar();}
return res*w;
}
const int N=2e5+9,mod=20070720+20061019+5250,base=131,dom=998244353;
int n,m,len[N],a[10000001],cnt[9];
char s[10000001];
ull b[N];
int pre[N],nxt[N];
void cut(int x) {pre[nxt[x]]=0,nxt[x]=0;}
void unite(int x,int y) {nxt[x]=y,pre[y]=x;}
namespace HT {
int hd[mod],nxt[mod],c[mod],tot;
pui vp[mod];
void add(pui x) {
int val=x.fi%mod,u=hd[val];
while(u&&vp[u]!=x) u=nxt[u];
if(!u) {vp[++tot]=x,c[tot]=1,nxt[tot]=hd[val],hd[val]=tot;}
else c[u]++;
}
void del(pui x) {
int val=x.fi%mod,u=hd[val];
while(u&&vp[u]!=x) u=nxt[u];
if(!u) throw 404;
else c[u]--;
}
int qry(pui x) {
int val=x.fi%mod,u=hd[val];
while(u&&vp[u]!=x) u=nxt[u];
return c[u];
}
}
int main() {
n=read(), m=read();
rep(i,1,n) len[i]=read(), cnt[len[i]]++;
b[0]=1; rep(i,1,100) b[i]=b[i-1]*base;
rep(i,1,m) {
int opt=read();
if(opt==1) {
int x=read(), y=read();
vi f(101); vector<ull> g(101);
for(int u=x,c=50;c;u=pre[u]) f[c--]=u;
for(int u=y,c=50;c<=100;u=nxt[u]) f[++c]=u;
rep(i,1,100) g[i]=g[i-1]*base+len[f[i]];
rep(l,1,50) if(f[l]) rep(r,51,100) if(f[r]&&r-l+1<=50) {
ull res=g[r]-g[l-1]*b[r-l+1];
HT::add(pui(res,r-l+1));
}
unite(x,y);
} else if(opt==2) {
int x=read(), y=nxt[x];
cut(x);
vi f(101); vector<ull> g(101);
for(int u=x,c=50;c;u=pre[u]) f[c--]=u;
for(int u=y,c=50;c<=100;u=nxt[u]) f[++c]=u;
rep(i,1,100) g[i]=g[i-1]*base+len[f[i]];
rep(l,1,50) if(f[l]) rep(r,51,100) if(f[r]&&r-l+1<=50) {
ull res=g[r]-g[l-1]*b[r-l+1];
HT::del(pui(res,r-l+1));
}
} else {
scanf("%s",s+1); int m=strlen(s+1), k=read();
rep(i,1,m) a[i]=s[i]-'0';
int ans=1;
if(k==1) {
rep(i,1,m) ans=1ll*ans*cnt[a[i]]%dom;
printf("%d\n",ans);
continue;
}
vector<ull> g(m+1);
rep(i,1,m) g[i]=g[i-1]*base+a[i];
rep(l,1,m-k+1) {
int r=l+k-1; ull res=g[r]-g[l-1]*b[r-l+1];
ans=1ll*ans*HT::qry(pui(res,k))%dom;
}
printf("%d\n",ans);
}
}
return 0;
}