Nowcoder 5733 M

作者: ffacs 分类: 题目 发布时间: 2020-06-09 14:41

题意

给定长度为 $n \le 200000$ 的序列,输出下标字典序最大的最长上升子序列

解法

首先 $n$ 这么大,肯定要用 $nlogn$ 的方法进行维护。那么难点在于下标字典序最大。 注意到一点,我们维护的数组,在任意时刻,当前位置的前一个一定是最接近自己的。比如如果当前更新到的是长度为7的 $LIS$ 的最后一个数字的最小值,那么当前数组里6位置元素的下标就一定是前面最接近自己的6的位置。

发表评论

电子邮件地址不会被公开。 必填项已用*标注