#P3646. Escape

    ID: 2841 传统题 1000ms 256MiB 尝试: 10 已通过: 5 难度: 9 上传者: 标签>难度分类省选/NOI-字符串后缀自动机endpos 等价类数据结构Link-Cut TreeCF2600KpmCup#1

Escape

Escape

题目背景

甘道夫和魔戒远征队误入了精灵的陷阱。他们必须回答石壁上的问题才能离开。KPM 还暗中给石壁上的修改操作加了密。

题目描述

石壁上最初有一个由小写英文字母组成的字符串 ss。之后会依次进行两类操作。

  • 查询。给出一个非空字符串 pp,问当前 ss 中有多少个不同的连续子串以 pp 为前缀。来自不同位置但内容相同的子串只计一次,pp 本身也可以计入。
  • 修改。给出一个经过加密的小写字母。将其解密,然后把得到的字母加到 ss 的最前面。修改对后续所有操作有效。

字母 a 至 z 分别编号为 00 至 2525。设加密字母编号为 cc,最近一次查询的答案为 lastanslastans,则解密后的编号为

(c+key⋅lastans) mod 26.(c+key\cdot lastans)\bmod 26.

第一次查询之前,lastans=0lastans=0。

输入格式

第一行一个非空字符串 ss。

第二行两个整数 key,mkey,m,其中 mm 为操作总数。

随后 mm 行,每行给出一次操作。

  • 0 p:查询当前 ss 中不同的以 pp 为前缀的子串数。
  • 1 c:给出加密后的字母 c,解密后加到 ss 的最前面。

输出格式

每次查询输出一行一个整数。

ababc
0 3
0 ab
1 a
0 a
5
11

样例解释

第一次查询的五个子串是 ab、aba、abc、abab、ababc。

修改后 ss 变为 aababc。第二次查询的子串是 a、aa、ab、aab、aba、abc、aaba、abab、aabab、ababc、aababc。

数据范围

0≤key≤100\le key\le10,所有输入字符串只含小写英文字母。

| 数据比例 | mm 与初始 ∣s∣|s| 的上界 | 加密参数 | | ---: | ---: | --- | | 10%10\% | 100100 | 无额外限制 | | 另有 40%40\% | 5000050000 | key=0key=0 | | 另有 50%50\% | 5000050000 | key>0key>0 |