103545: [Atcoder]ABC354 F - Useless for LIS

Problem Statement

You are given an integer sequence $A$ of length $N$.

For each $t = 1, 2, \dots, N$, determine whether $A_t$ is included in a longest increasing subsequence of $A$.

Here, $A_t$ is included in a longest increasing subsequence of $A$ if and only if the following holds:

• Let $L$ be the length of a longest increasing subsequence of $A$. There exists a strictly increasing integer sequence $i = (i_1, i_2, \dots, i_L) \ (i_1 < i_2 < \dots < i_L)$, where each element is between $1$ and $N$, inclusive, that satisfies all of the following conditions:

  • $A_{i_1} < A_{i_2} < \dots < A_{i_L}$.
  • $i_k = t$ for some $k \ (1 \leq k \leq L)$.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• The sum of $N$ across all test cases is at most $2 \times 10^5$.

Input

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Here, $\mathrm{case_i}$ represents the input for the $i$-th case. Each case is given in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Print the answers in the following format:

$\mathrm{answer}_1$
$\mathrm{answer}_2$
$\vdots$
$\mathrm{answer}_T$

Here, $\mathrm{answer}_i$ represents the output for the $i$-th case. For each case, let there be $m$ indices $t$ such that $A_t$ is included in a longest increasing subsequence of $A$, which are $i_1, i_2, \dots, i_m$ in ascending order. Print these in the following format:

$m$
$i_1$ $i_2$ $\cdots$ $i_m$

Sample Input 1

1
5
2 1 4 5 3

Sample Output 1

4
1 2 3 4

One of the longest increasing subsequences is $(2, 4, 5)$, with a length of $3$. Another longest increasing subsequence is $(1, 4, 5)$. However, no longest increasing subsequence includes $A_5$.

Therefore, print $1, 2, 3, 4$.

Sample Input 2

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

Sample Output 2

5
1 3 4 5 6
2
4 5

题目描述

你被给定一个长度为 $N$ 的整数序列 $A$。

对于每个 $t = 1, 2, \dots, N$，判断 $A_t$ 是否包含在一个最长的递增子序列中。

其中，$A_t$ 包含在一个最长的递增子序列中，当且仅当以下条件成立：

• 令 $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}$。
  • 存在某个 $k \ (1 \leq k \leq L)$ 使得 $i_k = t$。

你将处理 $T$ 个测试用例，分别解答它们。

限制条件

• $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