分数: 525 点
问题陈述
给你一个整数序列 给出了 A 长度 N.
对于每个 t = 1, 2, \dots, N,判断是否 A_t 包含在最长递增子序列中 A.
在这里, A_t 包含在最长递增子序列中 A 当且仅当以下成立:
-
让 L 是最长递增子序列的长度 A。存在严格递增的整数序列 i = (i_1, i_2, \dots, i_L) \ (i_1 < i_2 < \dots < i_L),其中每个元素位于 1 和 N,包含在内,满足以下所有条件:
- A_{i_1} < A_{i_2} < \dots < A_{i_L}.
- i_k = t 对于一些 k \ (1 \leq k \leq L).
你被给予 T 测试用例;解决它们中的每一个。
什么是最长递增子序列?
序列的子序列 A 是一个序列,可以通过从 A 不改变顺序。
序列的最长递增子序列 A 是以下序列的子序列 A 严格以最大可能长度递增。
约束
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 总和 N 在所有测试用例中最多 2 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里, \mathrm{case_i} 表示的输入 i第一个案例。每个案例均按以下格式给出:
N A_1 A_2 \cdots A_N
输出
按以下格式打印答案:
\mathrm{answer}_1
\mathrm{answer}_2
\vdots
\mathrm{answer}_T
在这里, \mathrm{answer}_i 表示输出 i第一个案例。对于每种情况,让有 m 指数 t 这样 A_t 包含在最长递增子序列中 A,它们是 i_1, i_2, \dots, i_m 按升序排列。按以下格式打印这些内容:
m i_1 i_2 \cdots i_m
示例输入 1
1 5 2 1 4 5 3
示例输出 1
4 1 2 3 4
最长的递增子序列之一是 (2, 4, 5),长度为 3。另一个最长递增子序列是 (1, 4, 5)。然而,最长递增子序列不包括 A_5.
因此,打印 1, 2, 3, 4.
示例输入 2
2 6 2 5 3 4 3 4 5 10000 1000 100 1 10
示例输出 2
5 1 3 4 5 6 2 4 5