33OJ
登录 注册

#P17809. [ICPC 2019 Nanchang R] Dynamic Suffix Array

[ICPC 2019 Nanchang R] Dynamic Suffix Array

题目描述

在计算机科学中,后缀数组是一个字符串所有后缀的排序后的数组。它是一种数据结构,用于全文索引、数据压缩算法以及文献计量学等领域。

假设 S[1,n]S[1,n] 是一个字符串,我们记 S[i,j]S[i,j] 为 SS 中从 ii 到 jj 的子串,并将后缀 ii 记作 S[i,n]S[i,n]。

字符串 SS 的后缀数组 AA 定义为一个整数数组,按字典序给出 SS 所有后缀的起始位置。这意味着,数组元素 A[i]A[i] 包含 SS 中第 ii 小的后缀的起始位置,因此对于每个 1<i≤n1<i\leq n,总有 S[A[i−1],n]<S[A[i],n]S[A[i-1],n] < S[A[i],n] 成立。

现在有一个空字符串 SS,你需要动态维护它的后缀数组。共有 qq 个事件,分为以下两种类型:

  • 1 c : 在 SS 的末尾追加一个字符 cc。保证 cc 是从小写英文字母 aa 到 zz 中均匀随机选取的。
  • 2 k (1≤k≤∣S∣1\leq k\leq |S|): 你需要报告 kk 在当前 SS 的后缀数组中的位置,即你需要报告后缀 kk 的排名。

请编写一个程序,高效地处理这些事件。

输入格式

输入的第一行包含一个整数 qq (2≤q≤10000002 \leq q \leq 1000000),表示事件的数量。

接下来的 qq 行,每行描述一个事件。保证第一个事件是第一种类型,且最后一个事件是第二种类型。

输出格式

对于每个第二种类型的事件,输出一行一个整数表示答案。

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 完成