P13968 [VKOSHP 2024] Classics

你可能已经熟悉了在一个数组中寻找最长上升子序列的经典问题。设 $a$ 是一个包含 $n$ 个整数的数组。一个子序列 $i_1 < i_2 < \ldots < i_k$ 被称为“上升”的，如果 $a_{i_1} < a_{i_2} < \ldots < a_{i_k}$。最长上升子序列即为长度最大的上升子序列。当然，我们不会让你解决这个经典问题；你需要解决一个更复杂的版本…… 一开始，数组 $a$ 为空。然后，数字 $1, 2, \ldots, n$ 依次被加入到数组中。数字 $i$ 被插入到数组的第 $p_i$ 个位置。数组中的位置编号为 $1$ 到 $k$，其中 $k$ 是当前数组的大小。当在一个大小为 $k$ 的数组的第 $p$ 个位置插入一个元素时，原本处于第 $p$ 到第 $k$ 个位置的所有元素都会向右移动一位，当前元素被放入空出的位置。 你的任务是在每次插入新元素后，输出当前数组中最长上升子序列的长度。

第一行包含一个整数 $n$（$1 \le n \le 200\,000$）——表示要插入的元素个数。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le i$）——$p_i$ 表示第 $i$ 个元素插入的位置。

输出 $n$ 个整数，依次表示每次插入新元素后，当前数组中最长上升子序列的长度。

第一个样例中的数组变化如下：$[] \to [1] \to [1, 2] \to [3, 1, 2] \to [3, 1, 4, 2] \to [3, 1, 4, 5, 2]$。 由 ChatGPT 4.1 翻译