#P3646. Escape
Escape
Escape
题目背景
甘道夫和魔戒远征队误入了精灵的陷阱。他们必须回答石壁上的问题才能离开。KPM 还暗中给石壁上的修改操作加了密。
题目描述
石壁上最初有一个由小写英文字母组成的字符串 。之后会依次进行两类操作。
- 查询。给出一个非空字符串 ,问当前 中有多少个不同的连续子串以 为前缀。来自不同位置但内容相同的子串只计一次, 本身也可以计入。
- 修改。给出一个经过加密的小写字母。将其解密,然后把得到的字母加到 的最前面。修改对后续所有操作有效。
字母 a 至 z 分别编号为 至 。设加密字母编号为 ,最近一次查询的答案为 ,则解密后的编号为
第一次查询之前,。
输入格式
第一行一个非空字符串 。
第二行两个整数 ,其中 为操作总数。
随后 行,每行给出一次操作。
0 p:查询当前 中不同的以 为前缀的子串数。1 c:给出加密后的字母c,解密后加到 的最前面。
输出格式
每次查询输出一行一个整数。
ababc
0 3
0 ab
1 a
0 a
5
11
样例解释
第一次查询的五个子串是 ab、aba、abc、abab、ababc。
修改后 变为 aababc。第二次查询的子串是 a、aa、ab、aab、aba、abc、aaba、abab、aabab、ababc、aababc。
数据范围
,所有输入字符串只含小写英文字母。
| 数据比例 | 与初始 的上界 | 加密参数 | | ---: | ---: | --- | | | | 无额外限制 | | 另有 | | | | 另有 | | |