题目详情
返回题库题目描述
给你一个长度为N的整数序列A。
对于每个t=1,2,…,N，判断At是否包含在A的最长递增子序列中。
这里，当且仅当下面的条件成立时，At才包含在A的最长递增子序列中：
设L是A的最长递增子序列的长度。存在一个严格递增的整数序列i=(i1,i2,…,iL)(i1<i2<⋯<iL)，其中每个元素都在1与N之间(含)，且满足以下所有条件：
- Ai1<Ai2<⋯<AiL.
- ik=t为某个k(1≤k≤L)。
给你T个测试用例，请逐个求解。
什么是最长递增子序列？
序列A的子序列是从A中抽取一些元素而不改变其顺序而得到的序列。
序列A的最长递增子序列是A的子序列，它以最大可能的长度严格递增。
输入描述
第一行输入T代表T组数据
接下来T*2行数据
每组数据第一行输入一个N，第二行输入数列$A_1,A_2,A_3,\cdots,A_N$
数据范围：
- 1≤T≤2×$10^{5}$
- 1≤N≤2×$10^{5}$
- 1≤Ai≤$10^{9}$
- 所有测试用例中N的总和最多为2×$10^{5}$。
输出描述
按以下格式打印答案
ans1
ans2
ans3
....
ansn
answeri代表第i个案例的输出结果。对于每种情况，让m索引t中的At包含在A的最长递增子序列中，这些子序列按升序排列为i1,i2,…,im。请按以下格式打印：
m
$i_1,i_2,i_3,\cdots,i_m$
提示
样例1：
其中一个最长的递增子序列是(2,4,5)，长度为3。另一个最长的递增子序列是(1,4,5)。然而，没有一个最长的递增子序列包括A5。
因此，打印1,2,3,4