← 返回题目列表

Codeforces · 2121/H

H. 冰宝贝

中文机器翻译题面 查看原题

整数数组 $$$a_1, a_2, \ldots, a_n$$$ 的最长非递减子序列是最长索引序列 $$$1 \leq i_1 \lt i_2 \lt \ldots \lt 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 \le k \le 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$$$ 整数:对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,输出所有合适数组中最长非递减子序列的最大长度。

示例

输入
复制

6
1
1 1
2
3 4
1 2
4
4 5
3 4
1 3
3 3
8
6 8
4 6
3 5
5 5
3 4
1 3
2 4
3 3
5
1 2
6 8
4 5
2 3
3 3
11
35 120
66 229
41 266
98 164
55 153
125 174
139 237
30 72
138 212
109 123
174 196

输出
复制

1 
1 1 
1 2 2 3 
1 2 2 3 3 3 4 5 
1 2 2 2 3 
1 2 3 4 5 6 7 7 8 8 9 

注意

在第一个测试用例中,唯一可能的数组是 $$$a = [1]$$$。该数组的最长非递减子序列的长度为$$$1$$$。

在第二个测试用例中,对于 $$$k = 2$$$,无论我们如何选择 $$$a_1$$$ 和 $$$a_2$$$ 的值,条件 $$$a_1 \gt 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$$$。