初始有 n 个分离的字符，字符集为数字 1-6。m 次操作：
1 i j连接 i 号字符和 j 号字符，使 j 排在 i 后面。保证 i 是一个字符串的末尾，j 是另一个字符串的开头。2 i在 i 号字符的后面切开。保证 i 不是字符串的末尾。3 k s给出一个长度不小于 k 的字符串 s，对 s 的每个长度为 k 的子串 t，求出向后 k 字符串为 t 的字符的个数，输出乘积模 998244353。定义某个字符的向后 k 字符串为：从该字符往后数，最近的 k 个字符依次连接得到的字符串（包括它本身）。
（n ≤ 2e5，m ≤ 3e5，k ≤ 50，Σ|s| ≤ 1e7，第 2 类操作的次数 c ≤ 1e3）
NOI 2017 是一次失败的经历......10 个小时切掉 0 道题，然后就回来学文化课了......
观察数据范围：
- 字符集很小
- k 很小
- 第 2 类操作很少
一个长度为 n 的字符串的长度不超过 k 的子串有 O(kn) 个。不妨直接用哈希表或 Trie 维护长度不超过 K=50 的子串（即向后 x 字符串，x = 1,2,...,K）的集合。
一次第 1 类操作的代价是 O(增加的子串的数目)。一次第 2 类操作的代价是
（学习了正解后）写的是 Trie。一开始直接 O(k|s|) 暴力查询，TLE 4 组。讲题的时候听说 Trie 可以，在“统计”里也看到有人写的是 Trie，再加上本地开 O2 之后跑得挺快，以为是常数问题，于是心里满是对出题人的怨气。再仔细一看，这个 Trie 怎么有 fail 边......
连了 fail 边的 Trie 就是 AC 自动机啦～通常来讲，AC 自动机只能离线处理，但是，这里的 Trie 存的是所有长度不超过 k 的子串。按照正确的顺序插入，fail 边直接连到了不能再改进的位置；也就是说，长度为 l 的串顺着 fail 边再走一步，得到的一定是长度为 l-1 的串。
由于只需求乘积，查询的时候读到不存在的边，直接停止输出 0 即可。否则，可能还得顺着 fail 边多走几步试试，但还是单次 O(|s|) 的。
其实还是一道不错的题，引导我们进行时间复杂度的分析。从寻求一个“好写的暴力”的角度，也能找到这个解法。然而，我当时没有找到。
小时候写代码是为了娱乐，后来写代码是为了升学，现在写代码又是为了娱乐。
const int N = 2e5 + 1, K = 50, S = 6, MOD = 998244353, L = 1e7 + 1, X = N*K + 1000*K*K;
int ptr, c[X][S], x[X], fail[X], l[N], r[N];
char s[L], a[N];
inline int go(char* s, int k)
{
int p = 0;
while (k--) p = c[p][int(*s++)];
return p;
}
inline void add(int p, char* s, int k, int d)
{
while (k--)
{
int& t = c[p][int(*s)];
if (!t) t = ++ptr, fail[t] = c[fail[p]][int(*s)];
x[p = t] += d;
++s;
}
}
int getL(char* s, int i)
{
rep (k, 1, K)
{
if (!i) return k-1;
*s++ = a[i];
i = l[i];
}
return K-1;
}
int getR(char* s, int i)
{
rep (k, 1, K)
{
if (!i) return k-1;
*s++ = a[i];
i = r[i];
}
return K-1;
}
void modify(int i, int j, int d)
{
int p = getL(s, i);
reverse(s, s+p);
int q = getR(s+p, j);
rep (i, 1, p+1) add(go(s+p-i, i), s+p, min(q, K-i), d);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
rep (i, 1, n+1)
{
int t;
scanf("%d", &t);
a[i] = --t;
if (!c[0][t]) c[0][t] = ++ptr;
++x[c[0][t]];
}
while (m--)
{
int o, i, j;
scanf("%d", &o);
if (o == 1)
{
scanf("%d%d", &i, &j);
modify(i, j, 1);
r[i] = j;
l[j] = i;
}
else if (o == 2)
{
scanf("%d", &i);
modify(i, r[i], -1);
l[r[i]] = 0;
r[i] = 0;
}
else
{
scanf("%s%d", s, &i);
int ans = 1, p = 0;
for (int k = 0; s[k]; ++k)
{
int t = c[p][s[k]-'1'];
if (!t)
{
ans = 0;
break;
}
if (k >= i-1)
{
ans = 1LL * ans * x[t] % MOD;
p = fail[t];
}
else
p = t;
}
printf("%d\n", ans);
}
}
return 0;
}祝大家戊戌年快乐！