AT_abc354_f [ABC354F] Useless for LIS

题目描述

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

对于 $t = 1, 2, \dots, N$，请判断 $A_t$ 是否有可能被包含在 $A$ 的最长严格递增子序列中。

$A_t$ 有可能被包含在 $A$ 的最长递增子序列中，指的是存在如下情况：

• 设最长递增子序列的长度为 $L$。存在一个长度为 $L$ 的严格递增的整数序列 $i = (i_1, i_2, \dots, i_L)$，满足以下条件：
  • $A_{i_1}, A_{i_2}, \dots, A_{i_L}$ 构成 $A$ 的一个最长严格递增子序列。
  • 存在某个 $k\ (1 \leq k \leq L)$ 使得 $i_k = t$。

给定 $T$ 组测试数据，请分别输出每组的答案。

最长递增子序列的定义如下：$A$ 的子序列是指从 $A$ 中取出若干元素，保持原有顺序得到的序列。$A$ 的最长递增子序列是指所有严格递增子序列中长度最大的那一个。

输入格式

输入按以下格式从标准输入读入。

$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$ 的最长递增子序列中，且这些 $t$ 升序排列为 $i_1, i_2, \dots, i_m$，则输出格式如下：

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

输入输出样例 #1

输入 #1

1
5
2 1 4 5 3

输出 #1

4
1 2 3 4

输入输出样例 #2

输入 #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

说明/提示

数据范围

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

样例解释 1

最长递增子序列之一为 $(2, 4, 5)$，长度为 $3$。$(1, 4, 5)$ 也是最长递增子序列之一。但是，没有包含 $A_5$ 的最长递增子序列。因此，应输出 $1, 2, 3, 4$。

由 ChatGPT 4.1 翻译