题目详情题解（0）讨论（0）提交记录（0）

CF2121H.Ice Baby

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

一个整数数组 a1,a2,…,ana_1, a_2, \ldots, a_n 的最长不下降子序列，指的是满足 1≤i1<i2<…<ik≤n1 \leq i_1 < i_2 < \ldots < i_k \leq n 且 ai1≤ai2≤…≤aika_{i_1} \leq a_{i_2} \leq \ldots \leq a_{i_k} 的最长的索引序列。该序列的长度定义为序列中元素的个数。例如，数组 a=[3,1,4,1,2]a = [3, 1, 4, 1, 2] 的最长不下降子序列的长度为 33。

现在给定两个整数数组 l1,l2,…,lnl_1, l_2, \ldots, l_n 和 r1,r2,…,rnr_1, r_2, \ldots, r_n。对于每个 1≤k≤n1 \leq k \leq n，解决如下问题：

  • 考虑所有长度为 kk 的整数数组 aa，使得对于每个 1≤i≤k1 \leq i \leq k，都有 li≤ai≤ril_i \leq a_i \leq r_i。在所有这样的数组中，求最长不下降子序列的最大长度。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 tt（1≤t≤1041 \leq t \leq 10^4），表示测试用例的数量。

每个测试用例的第一行包含一个整数 nn（1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^5），表示数组 ll 和 rr 的长度。

接下来的 nn 行，每行包含两个整数 lil_i 和 rir_i（1≤li≤ri≤1091 \leq l_i \leq r_i \leq 10^9）。

保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式

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

输入输出样例

  • 输入#1

    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 
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]a = [1]。该数组的最长不下降子序列长度为 11。

在第二个测试用例中，对于 k=2k = 2，无论如何选择 a1a_1 和 a2a_2，总有 a1>a2a_1 > a_2。因此，k=2k = 2 的答案为 11。

在第三个测试用例中，对于 k=4k = 4，可以选择数组 a=[5,3,3,3]a = [5, 3, 3, 3]。该数组的最长不下降子序列长度为 33。

在第四个测试用例中，对于 k=8k = 8，可以选择数组 a=[7,5,3,5,3,3,3,3]a = [7, 5, 3, 5, 3, 3, 3, 3]。该数组的最长不下降子序列长度为 55。

在第五个测试用例中，对于 k=5k = 5，可以选择数组 a=[2,8,5,3,3]a = [2, 8, 5, 3, 3]。该数组的最长不下降子序列长度为 33。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页