← 返回题目列表

AtCoder · abc354_f

I. 对于 LIS 无用

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

分数: 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