T268394 「GOI-R1」说书人

$$\pmb{\color{Gold}[\;我虽无意逐鹿，却知苍生苦楚\;]}$$ $$\pmb{\color{Gold}[\;只愿荡涤四方，护得浮世一隅\;]}$$ $$\pmb{\color{Gold}[\;那是璃月最初的『契约』，而现在最后的『契约』，也终于拟定了\;] }$$ $$\pmb{\color{Gold}[\;金石崩碎荡尘埃，盘山淤水尽为开\;]}$$ $$\pmb{\color{Gold}[\;创龙点睛得助力，盘桓碎引雨露来\;]}$$

璃月城东名叫『三碗不过港』的茶馆里，有一位名满全城的说书人——田铁嘴。 每天，田铁嘴都会在来喝茶的客人面前一遍遍讲述上古时代岩王帝君荡涤四方庇佑璃月的故事，博得阵阵掌声。 他有一个同门师兄，名气和他旗鼓相当，被人们称为『茶博士刘苏』。他们二人虽师出同门，却怀抱着不同的理念：田铁嘴喜好贴近市井，而刘苏讲究上达厅堂。二人平时互有切磋。 最近，刘苏向田铁嘴发起挑战，要和他一较高下。所以，田铁嘴想找出最受欢迎的作品。于是，田铁嘴找到了你，希望你能够统计出人们对他的作品的的满意度。 田铁嘴会给你一段字符串 $s$，这是他的作品的原文。每次说书后，观众们都会从中总结出一个**关键词** $key$。我们设关键词 $key$ **在 $s$ 中所有的结束位置的集合**为 $A$，**那么对于 $s$ 的一个子串 $t$，设其在 $s$ 中所有的结束位置的集合为 $B$，若 $B \subseteq A$（注意，此段已修改）**，那么我们称这段子串为一个**关键段落**，则这次说书的总满意度就是所有关键段落的满意度之和。 有时候，观众还会对同一个关键词更改他们的评价。如果某一个关键词被反复讲了很多遍，观众可能会感到厌烦，使得满意度降低；但是，如果这个关键词非常经典，可能听得越多，满意度越高。具体的，对于每次评价的更改，观众们会给出一个关键词，并商量出一个值 $x$，那么这个关键词所对应的关键段落的满意度都会加上 $x$。 由于这些都是新作，所以初始时所有的子串的满意度都是 $1$。 由于时间匆忙，你需要尽快统计出人们对这份作品的满意度，如果你帮助他赢过了刘苏，他会赠送你一把珍藏的『创龙点睛奇象』的扇子。 #### 形式化题意 给出一段字符串 $s$。设关键词 $key$ **在 $s$ 中所有的结束位置的集合**为 $A$。那么对于区间 $[l,r]$ 上的子串，若 $r \in A$，则称其为一个**关键段落**。你需要编写一个程序，维护一下两种操作： 1. 对于一个关键词 $key$，求其对应的所有的关键段落的权值之和。 2. 对于一个关键词 $key$，将其对应的所有的关键段落的权值加上 $x$。 对于每次操作一，输出答案。初始时人们对任何一段区间上的子串的满意度均为 $1$。

第一行两个正整数 $n$ 和 $q$。分别表示初始时给出的字符串长度和操作次数。 第三行给出一个长度为 $n$ 的字符串 $s$。 第 $4$ 行到第 $q + 3$ 行，每行若干个整数和一个字符串。具体如下： - 操作一：格式：`0 k`。其中 `k` 是一个字符串，表示输入的关键词。 - 操作二：格式：`1 k x`。其中 `k` 是一个字符串，表示输入的关键词；`x` 是一个正整数，表示满意度变化的值。 其中操作一与操作二含义同题目描述。

输出包括若干行。对于每一个操作一，输出一个整数，表示对应的结果。

### 样例解释 以 `bc` 为关键字时，关键段落有 `abcbc` `bcbc` `cbc` `abc` 各一个，`bc` `c` 各两个，初始时其满意度均为 $1$，故答案为 $8$。 以 `c` 为关键字时，关键段落有 `abcbc` `bcbc` `cbc` `abc` 各一个，`bc` `c` 各两个，初始时其满意度均为 $1$，故答案为 $8$。 以 `bc` 为关键字时，关键段落有 `abcbc` `bcbc` `cbc` `abc` 各一个，`bc` `c` 各两个，其满意度全部加上 $2$。 以 `bc` 为关键字时，关键段落有 `abcbc` `bcbc` `cbc` `abc` 各一个，`bc` `c` 各两个，其满意度在上一次修改中均被加上了 $2$，当前满意度均为 $3$，故答案为 $24$。 --- ### 数据范围 对于 $10\%$ 的数据，满足 $n \le 500,\;q \le 100$。 对于 $30\%$ 的数据，满足 $n \le 5000,\;q \le 10000$ 对于 $100\%$ 的数据，满足 $n \le 5 \times 10^5,\;q \le 10^5,\; \sum|k| \le 10^6$ 保证答案在 `int` 类型范围以内。