longest increasing subsequence 马甲系列汇总

LIS有很多马甲题：
300. Longest Increasing Subsequence
646. Maximum Length of Pair Chain
354. Russian Doll Envelopes

其中我觉得646 这个马甲穿的尤其漂亮。 大家还有什么补充的吗？ 吐槽和炫技都热烈欢淫

对于646，我有一个borrow 300 idea的想法，不过复杂度还是nlogn，没有标答里的解法2简洁。
假设我们有一个class叫tuple，定义如下,这里用python来prototype：
class my_tuple(object):
    def __init__(self, lo, hi, count):
        self.lo = lo
        self.hi = hi
        self.count = count # maintain the longest length count so far including this element
   
    def __lt__(self, other): # comparator, compare this object based on second element
        return self.hi < other.hi

为了讨论方便，假设我们每一个pair是(A,B)
initialize dp array，和LC300一样，我们称之为dp，我们称这里的pair array为pairs
首先sort pairs by 1st element of each pair
然后iterate through sorted pair array。其间对于每一个元素，首先用A构建my_tuple(dummy, A, dummy)的object，找其适合的插入位置，这里目的是将第一个元素和dp里面的第二个元素比
找到该位置之后，找其之前位置里面所有元素中最大的count值，则当前元素的count值为其+1，此时更新max_count
最后将当前元素的tuple object插入dp，根据第二个元素来插

这里的难点是“找其之前位置里面所有元素中最大的count值”，可以转化为find max element in prefix，用线段树可以做到每次操作logn
所以整个算法复杂度是nlogn

不过感觉绕了很多弯子，没有标答的nlogn简洁

我这种想法有种脱裤子放屁的感觉