#P9179. AC/DC

    ID: 5261 传统题 8000ms 256MiB 尝试: 3 已通过: 3 难度: 8 上传者: 标签>CF2500提高+/省选-根号分块后缀自动机按长度传播出现次数子串哈希双哈希随机哈希暴力枚举计数排序2022

AC/DC

Problem 1008. AC/DC

题目描述

J 喜欢弹电吉他,尤其喜欢著名的 Gibson SG Standard 型号。他总是用自己的 Gibson SG Standard 创作音乐。

他创作的一首曲子由若干音符组成。形式化地,一首曲子可以看作一个仅由小写字母组成的字符串,不同的字母代表不同的音符。曲子的一个子串称为一个乐句。

最初,J 有一首长度为 nn 的曲子。为了创作新的音乐,J 可以进行以下三种操作,其中查询统计所有起点,允许出现位置重叠:

  • 1 c:在当前曲子的末尾插入一个音符 cc。
  • 2:删除当前曲子开头的音符。
  • 3 t:查询乐句 tt 在当前曲子中出现的次数。

现在,J 正忙于制作新专辑,并邀请你一起创作音乐。你能帮助他吗?

输入格式

第一行包含一个整数 TT(1≤T≤51\le T\le 5),表示测试用例的数量。对于每个测试用例:

第一行包含一个长度为 nn 的字符串 SS(1≤n≤1051\le n\le 10^5),表示初始曲子。

下一行包含一个整数 mm(1≤m≤1051\le m\le 10^5),表示操作次数。

接下来 mm 行,第 ii 行包含一个形如 1 c'、2 或 3 t' 的操作。

定义上一次查询的答案为 lastanslastans,每组数据开始时 lastans=0lastans=0,仅查询后更新。式中的 ⊕\oplus 表示按位异或。

  • 对于 1 c',实际操作中的字符为$$c=((c'-\text{'a'})\oplus lastans)\bmod 26+\text{'a'}.$$
  • 对于 3 t',实际操作中的字符串满足:对于每个 1≤i≤∣t∣1\le i\le |t|,$$t_i=((t'_i-\text{'a'})\oplus lastans)\bmod 26+\text{'a'}.$$

保证 cc 是小写字母,tt 是仅由小写字母组成的字符串。所有测试用例中 tt 的长度之和不超过 5×1065\times 10^6。

注意,字符串 SS 可能被删除为空串,但保证此时不会出现类型为 2 的操作。

输出格式

对于每个查询 3 t,输出一行一个整数,表示答案。

样例

1
abcbaba
5
3 ab
3 c
1 a
2
3 da
2
3
1

来源:2022 中国大学生程序设计暑期联赛第 5 场(福州大学)。

原 PDF 题面