#P9179. AC/DC
AC/DC
Problem 1008. AC/DC
题目描述
J 喜欢弹电吉他,尤其喜欢著名的 Gibson SG Standard 型号。他总是用自己的 Gibson SG Standard 创作音乐。
他创作的一首曲子由若干音符组成。形式化地,一首曲子可以看作一个仅由小写字母组成的字符串,不同的字母代表不同的音符。曲子的一个子串称为一个乐句。
最初,J 有一首长度为 的曲子。为了创作新的音乐,J 可以进行以下三种操作,其中查询统计所有起点,允许出现位置重叠:
1 c:在当前曲子的末尾插入一个音符 。2:删除当前曲子开头的音符。3 t:查询乐句 在当前曲子中出现的次数。
现在,J 正忙于制作新专辑,并邀请你一起创作音乐。你能帮助他吗?
输入格式
第一行包含一个整数 (),表示测试用例的数量。对于每个测试用例:
第一行包含一个长度为 的字符串 (),表示初始曲子。
下一行包含一个整数 (),表示操作次数。
接下来 行,第 行包含一个形如 1 c'、2 或 3 t' 的操作。
定义上一次查询的答案为 ,每组数据开始时 ,仅查询后更新。式中的 表示按位异或。
- 对于
1 c',实际操作中的字符为$$c=((c'-\text{'a'})\oplus lastans)\bmod 26+\text{'a'}.$$ - 对于
3 t',实际操作中的字符串满足:对于每个 ,$$t_i=((t'_i-\text{'a'})\oplus lastans)\bmod 26+\text{'a'}.$$
保证 是小写字母, 是仅由小写字母组成的字符串。所有测试用例中 的长度之和不超过 。
注意,字符串 可能被删除为空串,但保证此时不会出现类型为 2 的操作。
输出格式
对于每个查询 3 t,输出一行一个整数,表示答案。
样例
1
abcbaba
5
3 ab
3 c
1 a
2
3 da
2
3
1
来源:2022 中国大学生程序设计暑期联赛第 5 场(福州大学)。