O(n log n) LIS

一句话理解

O(n log n) LIS：维护长度为 k 的最小结尾。

为什么要学

tails 数组二分。

讲解

tails[k] 是长度 k+1 的 LIS 的最小末尾。新元素二分替换。

例子

贪心让同样长度的末尾尽量小，更易接后面。

常见错误

• 求方案时只得到长度，要额外记录。
• 非严格递增用 upper_bound 还是 lower 搞反。