蚯蚓排队
思路上还是比较水的（然而扬言1h \(AC\) 的某人被许多小问题d了半天），操作一，二对于每个队伍都直接进行维护就好，关键是操作三（明明就是取个子串非不说人话）。
Analysis
- 简化题意：给定一串字符（蚯蚓），三种操作：
- \(opt=1\) 让第 \(i\) 与 \(j\) 个字符合并。
- \(opt=2\) 让第 \(i\) 与 \(j\) 个字符分离。
- \(opt=3\) 再给定一个字符串 \(s\) 与一个整数 \(k\)，枚举每一个 \(s\) 的字串 \(\overline{s}\)，将其与蚯蚓串的每个长度相同（即为 \(k\)）的子串匹配，求每个 \(\overline{s}\) 可以匹配到的个数 \(d_i\)，求 \(\Pi_{d_i}\mod 998244353\)。
- 数据范围 \(k\leqslant 50\) 告诉我们直接维护暴力不同 \(k\) 值下的蚯蚓信息没有问题，对于某个操作显然只有待修位置的 \(k\) 长度附近的信息会受影响，提出来合并一下哈希值即可。
- 平板电视还能被卡，建议自己重修 \(OI\)。
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define int unsigned long long
#define id(x) x-'0'
const int kk=1e7+100,N=2e5+5,base=131,mod=998244351;
using namespace std;
__gnu_pbds::cc_hash_table<int,int> cnt;
int n,m;
int fac[60],chs[N],nxt[N],pre[N];
char ch[kk];
inline void solve(int opt,int x,int y){
nxt[x]=y,pre[y]=x;
for(int len=2;len<=50;++len){
int ne(0),pr(0);
for(int i=x;i&&pr<=len-2;i=pre[i]) ++pr;
for(int i=y;i&&pr+ne<len;i=nxt[i]) ++ne;
if(pr+ne<len) break;pr=x;
for(int i=1;i<len-1&&pre[pr];++i) pr=pre[pr];
ne=pr;int hh(0);
for(int i=1;i<=len;++i){
hh=hh*base+chs[ne];
ne=nxt[ne];
}
while(1){
H.mdf(hh,opt==1?1:-1);
if(!ne||pr==x) break;
hh-=chs[pr]*fac[len-1];
pr=nxt[pr];
hh=hh*base+chs[ne];
ne=nxt[ne];
}
}
if(opt==2) nxt[x]=pre[y]=0;
}
inline void get_ans(char *s,int k){
int ans=1,n(strlen(s+1));
if(k==1){
for(int i=1;i<=n;++i) ans=1ll*ans*cnt[id(s[i])]%mod;
write(ans);return;
}
int hash(0);
for(int i=1;i<=k;++i) hash=hash*base+id(s[i]);
int l=1,r=k+1;
while(1){
ans=1ll*ans*H.qry(hash)%mod;
if(r>n||!ans) break;
hash-=(id(s[l++]))*fac[k-1];
hash=hash*base+id(s[r++]);
}
write(ans);return;
}
signed main(){
fac[0]=1;
for(int i=1;i<=50;++i) fac[i]=fac[i-1]*base;
n=read(),m=read();
for(int i=1;i<=n;++i) chs[i]=read(),cnt[chs[i]]++;
while(m--){
int op(read()),a,b,k;
switch(op){
case 1:a=read(),b=read();solve(op,a,b);break;
case 2:a=read();solve(op,a,nxt[a]);break;
default:scanf("%s",ch+1);k=read();get_ans(ch,k);break;
}
}
return 0;
}