CF1794C Scoring Subsequences

一个序列 $[s_1, s_2, \ldots, s_d]$ 的分数定义为 $\displaystyle \frac{s_1 \cdot s_2 \cdot \ldots \cdot s_d}{d!}$，其中 $d! = 1 \cdot 2 \cdot \ldots \cdot d$。特别地，空序列的分数为 $1$。 对于序列 $[s_1, s_2, \ldots, s_d]$，设 $m$ 为其所有子序列中的最大分数。其代价定义为分数为 $m$ 的子序列的最大长度。 给定一个长度为 $n$ 的非递减整数序列 $[a_1, a_2, \ldots, a_n]$，即满足 $a_1 \leq a_2 \leq \ldots \leq a_n$。对于每个 $k=1,2,\ldots,n$，求序列 $[a_1, a_2, \ldots, a_k]$ 的代价。 如果序列 $x$ 可以通过从序列 $y$ 中删除若干（可能为零或全部）元素得到，则称 $x$ 是 $y$ 的子序列。

每个测试点包含多组测试数据。第一行包含测试用例个数 $t$（$1 \leq t \leq 10^4$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示给定序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示给定的序列。保证该序列为非递减序列。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每组测试数据，输出 $n$ 个整数，依次表示 $[a_1], [a_1, a_2], \ldots, [a_1, a_2, \ldots, a_n]$ 的代价。

在第一个测试用例中： - $[1]$ 的所有子序列中最大分数为 $1$。子序列 $[1]$ 和 $[]$（空序列）的分数都是 $1$，因此 $[1]$ 的代价为 $1$。 - $[1, 2]$ 的所有子序列中最大分数为 $2$。只有子序列 $[2]$ 的分数为 $2$，因此 $[1, 2]$ 的代价为 $1$。 - $[1, 2, 3]$ 的所有子序列中最大分数为 $3$。子序列 $[2, 3]$ 和 $[3]$ 的分数为 $3$，因此 $[1, 2, 3]$ 的代价为 $2$。 因此，该测试用例的答案为 $1\:\:1\:\:2$，分别对应 $[1], [1, 2], [1, 2, 3]$ 的代价。 由 ChatGPT 4.1 翻译