CF2121H Ice Baby

一个整数数组 $a_1, a_2, \ldots, a_n$ 的最长不下降子序列，指的是满足 $1 \leq i_1 < i_2 < \ldots < i_k \leq n$ 且 $a_{i_1} \leq a_{i_2} \leq \ldots \leq a_{i_k}$ 的最长的索引序列。该序列的长度定义为序列中元素的个数。例如，数组 $a = [3, 1, 4, 1, 2]$ 的最长不下降子序列的长度为 $3$。 现在给定两个整数数组 $l_1, l_2, \ldots, l_n$ 和 $r_1, r_2, \ldots, r_n$。对于每个 $1 \leq k \leq n$，解决如下问题： - 考虑所有长度为 $k$ 的整数数组 $a$，使得对于每个 $1 \leq i \leq k$，都有 $l_i \leq a_i \leq r_i$。在所有这样的数组中，求最长不下降子序列的最大长度。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组 $l$ 和 $r$ 的长度。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数：对于每个 $k$ 从 $1$ 到 $n$，输出所有满足条件的数组中最长不下降子序列的最大长度。

在第一个测试用例中，唯一可能的数组为 $a = [1]$。该数组的最长不下降子序列长度为 $1$。 在第二个测试用例中，对于 $k = 2$，无论如何选择 $a_1$ 和 $a_2$，总有 $a_1 > a_2$。因此，$k = 2$ 的答案为 $1$。 在第三个测试用例中，对于 $k = 4$，可以选择数组 $a = [5, 3, 3, 3]$。该数组的最长不下降子序列长度为 $3$。 在第四个测试用例中，对于 $k = 8$，可以选择数组 $a = [7, 5, 3, 5, 3, 3, 3, 3]$。该数组的最长不下降子序列长度为 $5$。 在第五个测试用例中，对于 $k = 5$，可以选择数组 $a = [2, 8, 5, 3, 3]$。该数组的最长不下降子序列长度为 $3$。 由 ChatGPT 4.1 翻译