F - Useless for LIS

Contest Duration: 2024-05-18(Sat) 12:00 - 2024-05-18(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Useless for LIS Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $525$ 点

問題文

長さ $N$ の整数列 $A$ が与えられます。

$t = 1, 2, \dots ,N$ について、 $A_t$ が $A$ の最長増加部分列に含まれることがあるか判定してください。

$A_t$ が $A$ の最長増加部分列に含まれることがあるとは、以下のことをいいます。

最長増加部分列の長さを $L$ とする。各要素が $1$ 以上 $N$ 以下の単調増加な整数列 $i = (i_1, i_2, \dots ,i_L) \ (i_1 < i_2 < \dots < i_L)$ であって以下をすべて満たすものが存在する。
- $A_{i_1} < A_{i_2} < \dots < A_{i_L}$
- ある $k \ (1 \leq k \leq L)$ が存在して $i_k = t$ である

$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$ 番目のケースの出力を意味する。各ケースについては、次の通りである。

$A_t$ が $A$ の最長増加部分列に含まれることがある $t$ が $m$ 個存在し、昇順に $i_1, i_2, \dots ,i_m$ であったとする。このとき、以下の形式で出力せよ。

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

入力例 1Copy

Copy

1
5
2 1 4 5 3

出力例 1Copy

Copy

4
1 2 3 4

最長増加部分列の $1$ つは $(2, 4, 5)$ で、長さは $3$ です。 $(1, 4, 5)$ も最長増加部分列の $1$ つです。しかし、 $A_5$ を含む最長増加部分列はありません。

よって、 $1, 2, 3, 4$ を出力します。

入力例 2Copy

Copy

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

出力例 2Copy

Copy

Score : $525$ points

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.

What is a longest increasing subsequence?

A subsequence of a sequence $A$ is a sequence that can be derived by extracting some elements from $A$ without changing the order.

A longest increasing subsequence of a sequence $A$ is a subsequence of $A$ that is strictly increasing with the greatest possible length.

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 1Copy

Copy

1
5
2 1 4 5 3

Sample Output 1Copy

Copy

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 2Copy

Copy

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

Sample Output 2Copy

Copy