A5835. 「HNOI2019」JOJO
编程题
NOI/NOI+/CTSC
知识点
题目描述
JOJO 的奇幻冒险是一部非常火的漫画。漫画中的男主角经常喜欢连续喊很多的「欧拉」或者「木大」。
为了防止字太多挡住漫画内容，现在打算在新的漫画中用 $x$ 欧拉或者 $x$ 木大表示有 $x$ 个欧拉或者木大。
为了简化内容我们现在用字母表示喊出的话。
我们用数字和字母来表示一个串，例如：
一开始漫画中什么话都没有，接下来你需要依次实现 $n$ 个操作，总共只有 $2$ 种操作：
- 第一种：
- 第二种：
众所周知空条承太郎十分聪明，现在迪奥已经被打败了，他开始考虑自己的漫画中的一些问题：
对于一个串的每个前缀 $A$，都有一个最长的比它短的前缀 $B$ 与前缀 $A$ 的一个后缀匹配，设这个最长的前缀 $B$ 的长度为 $L$。$L$ 为 $0$ 时意味着 $B$ 是一个空串。
每一次操作后，你都需要将当前的串的所有前缀的 $L$ 求和并对 $998244353$ 取模输出告诉空条承太郎，好和他的白金之星算出的答案对比。比如
为了防止字太多挡住漫画内容，现在打算在新的漫画中用 $x$ 欧拉或者 $x$ 木大表示有 $x$ 个欧拉或者木大。
为了简化内容我们现在用字母表示喊出的话。
我们用数字和字母来表示一个串，例如：
2 a 3 b 表示的串就是 aabbb。一开始漫画中什么话都没有，接下来你需要依次实现 $n$ 个操作，总共只有 $2$ 种操作：
- 第一种：
1 x c：在当前漫画中加入 $x$ 个 $c$，表示在当前串末尾加入 $x$ 个 $c$ 字符。保证当前串是空串或者串尾字符不是 $c$；- 第二种：
2 x：觉得漫画没画好，将漫画还原到第 $x$ 次操作以后的样子，表示将串复原到第 $x$ 次操作后的样子，如果 $x=0$ 则是将串变成空串。如果当前串是 bbaabbb，第 $4$ 次操作后串是 bb，则 2 4 会使 bbaabbb 变成 bb，保证 $x$ 小于当前操作数。众所周知空条承太郎十分聪明，现在迪奥已经被打败了，他开始考虑自己的漫画中的一些问题：
对于一个串的每个前缀 $A$，都有一个最长的比它短的前缀 $B$ 与前缀 $A$ 的一个后缀匹配，设这个最长的前缀 $B$ 的长度为 $L$。$L$ 为 $0$ 时意味着 $B$ 是一个空串。
每一次操作后，你都需要将当前的串的所有前缀的 $L$ 求和并对 $998244353$ 取模输出告诉空条承太郎，好和他的白金之星算出的答案对比。比如
bbaaabba 的 $L$ 分别是 $0, 1, 0, 0, 0, 1, 2, 3$，所以对于这个串的答案就是 $7$。输入格式
第一行包括一个正整数 $n$，表示操作数量。
接下来 $n$ 行每行包含一个操作，操作格式如题目描述所示，例如：
-
-
保证数据合法。
接下来 $n$ 行每行包含一个操作，操作格式如题目描述所示，例如：
-
1 x c-
2 x保证数据合法。
输出格式
仅包含 $n$ 行，第 $i$ 行一个整数，表示 $i$ 个操作之后串的答案。
输入输出样例
输入 #1
11 1 2 a 1 3 b 1 2 a 1 1 b 2 2 1 3 a 1 2 b 2 6 2 5 1 7 a 1 5 c
输出 #1
1 1 4 7 1 6 13 6 1 14 14
说明/提示
$20\%$ 的数据满足 $n\le 300$，对于每个 $1$ 操作中的 $x\le 300$；
另有 $30\%$ 的数据满足 $n\le 10^5$，且对于每个 $1$ 操作中的 $x=1$；
另有 $30\%$ 的数据满足 $n\le 10^5$，且不含 $2$ 操作；
$100\%$ 的数据满足 $n\le 10^5$，且每个 $1$ 操作中的 $x\le 10^4$。
另有 $30\%$ 的数据满足 $n\le 10^5$，且对于每个 $1$ 操作中的 $x=1$；
另有 $30\%$ 的数据满足 $n\le 10^5$，且不含 $2$ 操作；
$100\%$ 的数据满足 $n\le 10^5$，且每个 $1$ 操作中的 $x\le 10^4$。