题目描述
蚯蚓幼儿园有nn 只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。
所有蚯蚓用从11 到nn 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过66 。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。
神刀手将会依次进行mm 次操作，每个操作都是以下三种操作中的一种：
给出ii 和jj ，令ii 号蚯蚓与jj 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令jj 号蚯蚓紧挨在ii 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。
给出ii ，令ii 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后，ii 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。
- 给出一个正整数kk 和一个长度至少为kk 的数字串ss ，对于ss 的每个长度为kk 的连续子串tt （这样的子串共有|s| - k + 1∣s∣−k+1 个，其中|s|∣s∣ 为ss 的长度），定义函数f(t)f(t) ，询问所有这些f(t)f(t) 的乘积对998244353998244353 取模后的结果。其中f(t)f(t) 的定义如下： 对于当前的蚯蚓队伍，定义某个蚯蚓的向后kk 数字串为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的kk 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足kk只，则其没有向后kk 数字串。例如蚯蚓的队伍为1010 号蚯蚓在队首，其后是2222 号蚯蚓，其后是33 号蚯蚓（为队尾），这些蚯蚓的长度分别为44 、55 、66 ，则1010 号蚯蚓的向后33 数字串 为456，2222 号蚯蚓没有向后33 数字串，但其向后22 数字串为56，其向后11 数字串为5。
而f(t)f(t) 表示所有蚯蚓中，向后kk 数字串恰好为tt 的蚯蚓只数。
输入输出格式
输入格式：
输入文件的第一行有两个正整数n,mn,m ，分别表示蚯蚓的只数与操作次数。
第二行包含nn 个不超过66 的正整数，依次表示编号为1, 2, \dots , n1,2,…,n 的蚯蚓的长度。
接下来mm 行，每行表示一个操作。每个操作的格式可以为：
1 i j(1 \leqslant i, j \leqslant n)(1⩽i,j⩽n) 表示：令ii 号与jj 号蚯蚓所在的两个队伍合并为一个队伍，新队伍中，jj 号蚯蚓紧挨在ii 号蚯蚓之后。保证在此操作之前，ii 号蚯蚓在某个队伍的队尾，jj 号蚯蚓在某个队伍的队首，且两只蚯蚓不在同一个队伍中。2 i(1 \leqslant i \leqslant n)(1⩽i⩽n) 表示：令ii 号蚯蚓与紧挨其后一个蚯蚓分离为两个队伍。保证在此操作之前，ii 号蚯蚓不是某个队伍的队尾。3 s k（kk 为正整数，ss 为一个长度至少为kk 的数字串）表示：询问ss 的每个长度为kk 的子串tt 的f(t)f(t) 的乘积，对998244353998244353 取模的结果。f(t)f(t) 的定义见题目描述。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。
输入文件可能较大，请不要使用过于缓慢的读入方式。
输出格式：
依次对于每个形如3 s k的操作，输出一行，仅包含一个整数，表示询问的结果。
题目大意：
一个初始全为单个元素的集合，支持合并，分裂，查询s,k求出s所有长度为k的子串在现有的序列中出现的次数的乘积。
题解：
①用链表记录nxt[],pre[]来模拟分裂，合并；
②考虑到k<=50,意思就是我们只需要维护长度在50以内串，外加查询其出现的次数。而分裂操作c并不多，意味着合并也并不多。暴力维护即可:每次合并分裂时枚举跨过断点前后50位以内的串修改。
③用hash散列表来修改和查询，由于hash的模值比较大，无法开下所有v值，就可以将v类似于存边存进v%sz里，每次修改和查询暴力枚举一遍，复杂度几乎为O(1)
#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 200010
#define M 11000000
#define base 1000000007
#define mod 998244353
#define ull unsigned long long
using namespace std;
int n,m,pre[N],nxt[N];
char tmp[M],*P = tmp,*s,a[N];
ull H[M],pw[M];
char gc(){
static char *p1,*p2,s[];
if(p1==p2) p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
int rd(){
int x = ,f = ; char c = gc();
while(c<''||c>'') {if(c=='-') f = -; c = gc();}
while(c>=''&&c<='') {x = x * + c - ''; c = gc();}
return x * f;
}
int rd(char *c){
char *st = c;
do *c = gc(); while(*c<''||*c>'');
do *++c = gc(); while(*c>=''&&*c<='');
*c = ;
return c - st;
}
struct Edge{ull v; int nt,w;};
const int sz = 1e7;
struct HASH{
Edge E[sz + ]; int o,hd[sz + ];
int& adde(ull v){
E[++o] = (Edge){v,hd[v%sz],}; hd[v%sz] = o;
return E[o].w;
}
int& operator [] (ull v){
for(int i = hd[v%sz];i;i=E[i].nt)
if(E[i].v==v) return E[i].w;
return adde(v);
}
int val(ull v){
for(int i = hd[v%sz];i;i=E[i].nt)
if(E[i].v==v) return E[i].w;
return ;
}
}Hash;
void cal(int y,int x){
static char S[N]; int len = ,fg;
int st;for(st = y;pre[st]&&len<=;st = pre[st],len++); fg = ++len;
int ed;for(ed = y;nxt[ed]&&len<=;ed = nxt[ed],len++);
len = ; //S[++len] = a[st];
for(int i = st;nxt[i];i = nxt[i]) S[++len] = a[i];
S[++len] = a[ed];
for(int i = ;i <= len;i++) H[i] = H[i - ]*base + S[i];
for(int i = fg;i <= len;i++)
for(int j = max(i - ,);j < fg - ;j++){
Hash[H[i] - H[j] * pw[i - j]]+=x;
}
}
int main()
{ //freopen("mzoj1112.in","r",stdin);
//freopen("mzoj1112.out","w",stdout);
n = rd(); m = rd();
for(int i = pw[] = ;i < M;i++) pw[i] = pw[i - ] * base;
for(int i = ;i <= n;i++) Hash[a[i] = rd() + '']++;
for(int i = ,typ,x,y,len,k;i <= m;i++){
typ = rd();
if(typ==) {
x = rd(); y = rd();
pre[y] = x; nxt[x] = y;
cal(y,);
}
else if(typ==){
x = rd(); y = nxt[x];
cal(y,-);
pre[y] = nxt[x] = ;
}
else{
s = P; len = rd(s+); P += len + ; k = rd();
ull ans = ;
for(int i = ;i <= len;i++){
H[i] = H[i - ]*base + s[i];
if(i>=k) {
ull temp = H[i] - H[i - k] * pw[k];
ans = ans * Hash.val(temp) % mod;
}
}
printf("%llu\n",ans);
}
}
return ;
}//by tkys_Austin;