对 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 \lt i_2 \lt \dots \lt i_L$),其中每个元素都在 $1$ 到 $N$ 之间(含端点),且满足以下所有条件:

• $A_{i_1} \lt A_{i_2} \lt \dots \lt A_{i_L}$。
• 对某个 $k$($1 \le k \le L$),有 $i_k = t$。

本题有 $T$ 组测试用例,请分别求解。

什么是最长上升子序列?

序列 $A$ 的子序列,是指从 $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$ 组用例的输出。对每组用例,设满足「$A_t$ 被包含在 $A$ 的某个最长上升子序列中」的下标 $t$ 有 $m$ 个,按升序为 $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, 4, 5)$,长度为 $3$。另一个最长上升子序列是 $(1, 4, 5)$。但是,不存在包含 $A_5$ 的最长上升子序列。

因此输出 $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 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 所有测试用例的 $N$ 之和不超过 $2 \times 10^5$