#P17809. [ICPC 2019 Nanchang R] Dynamic Suffix Array
[ICPC 2019 Nanchang R] Dynamic Suffix Array
题目描述
在计算机科学中,后缀数组是一个字符串所有后缀的排序后的数组。它是一种数据结构,用于全文索引、数据压缩算法以及文献计量学等领域。
假设 是一个字符串,我们记 为 中从 到 的子串,并将后缀 记作 。
字符串 的后缀数组 定义为一个整数数组,按字典序给出 所有后缀的起始位置。这意味着,数组元素 包含 中第 小的后缀的起始位置,因此对于每个 ,总有 成立。
现在有一个空字符串 ,你需要动态维护它的后缀数组。共有 个事件,分为以下两种类型:
1 c: 在 的末尾追加一个字符 。保证 是从小写英文字母 到 中均匀随机选取的。2 k(): 你需要报告 在当前 的后缀数组中的位置,即你需要报告后缀 的排名。
请编写一个程序,高效地处理这些事件。
输入格式
输入的第一行包含一个整数 (),表示事件的数量。
接下来的 行,每行描述一个事件。保证第一个事件是第一种类型,且最后一个事件是第二种类型。
输出格式
对于每个第二种类型的事件,输出一行一个整数表示答案。
10
1 t
1 s
2 2
1 r
1 w
1 f
1 t
2 2
1 q
2 2
1
3
4
提示
翻译由 DeepSeek V4 Pro 完成