T357466 最长上升子序列 - 最长递增子序列 V2

数组 A 包含 N 个整数。设 S 为 A 的子序列且 S 中的元素是递增的，则 S 为 A 的递增子序列。如果 S 的长度是所有递增子序列中最长的，则称 S 为 A 的最长递增子序列（ LIS ）。 A 的 LIS 可能有很多个。例如 A 为： 1 3 2 0 4 ， 1 3 4 ， 1 2 4 均为 A 的 LIS 。其中元素 1 和 4 一定会出现在 LIS 当中，元素 2 和 3 可能会出现在 LIS 当中，元素 0 一定不会出现在 LIS 当中。给出数组 A ，输出哪些数可能出现在 LIS 中，哪些数一定出现在 LIS 中。输出数字对应的下标，下标编号从 1 开始，编号为 1−N 。例如： 1 3 2 0 4 ，可能出现的元素为 3 和 2 ，对应的下标为 2 和 3 。一定出现的元素为 1 和 4 ，对应下标为 1 和 5 . 输入格式 第 1 行： 1 个数 N ，表示数组的长度。 (1≤N≤50000) 第 2∼N+1 行：每行 1 个数 A[i] ，表示数组的元素 (0≤A[i]≤109) 输出格式 第 1 行：可能出现在 LIS 中的数的下标，中间用空格分隔。（输出的下标按照递增排序） 第 2 行：一定会出现在 LIS 中的数的下标，中间用空格分隔。（输出的下标按照递增排序） 输入样例 5 1 3 2 0 4 输出样例 A:2 3 B:1 5

无

无

无