P17809 [ICPC 2019 Nanchang R] Dynamic Suffix Array

在计算机科学中，后缀数组是一个字符串所有后缀的排序后的数组。它是一种数据结构，用于全文索引、数据压缩算法以及文献计量学等领域。 假设 $S[1,n]$ 是一个字符串，我们记 $S[i,j]$ 为 $S$ 中从 $i$ 到 $j$ 的子串，并将后缀 $i$ 记作 $S[i,n]$。 字符串 $S$ 的后缀数组 $A$ 定义为一个整数数组，按字典序给出 $S$ 所有后缀的起始位置。这意味着，数组元素 $A[i]$ 包含 $S$ 中第 $i$ 小的后缀的起始位置，因此对于每个 $1

输入的第一行包含一个整数 $q$ ($2 \leq q \leq 1000000$)，表示事件的数量。 接下来的 $q$ 行，每行描述一个事件。保证第一个事件是第一种类型，且最后一个事件是第二种类型。

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

翻译由 DeepSeek V4 Pro 完成