Useless for LIS

题目描述

你被给定一个长度为 $N$ 的整数序列 $A$。 对于每个 $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}。

对于某个 $k \ (1 \leq k \leq L)$ 有 $i_k = t$。

给定 $T$ 个测试用例；请对每个测试用例求解。

输入格式

输入从标准输入给出，格式如下： $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
5
2 1 4 5 3

4
1 2 3 4

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

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$。一个最长严格递增子序列是 $(2, 4, 5)$，长度为 $3$。另一个最长严格递增子序列是 $(1, 4, 5)$。然而，没有任何最长严格递增子序列包含 $A_5$。 因此，输出 $1, 2, 3, 4$。

标签: AtCoder|abc354F

来源

AtCoder|abc354F