最长上升子序列(三)

题号：NC207967
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中按数值(注：区别于按单个字符的ASCII码值)进行比较的字典序最小的那个）

数据范围： $0 \le n \le 200000 , 0 \le arr_i \le 1000000000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例1

复制

[2,1,5,3,6,4,8,9,7]

复制

[1,3,4,8,9]

示例2

复制

[1,2,8,6,4]

复制

[1,2,4]

其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）