\(O(n \log n)\)的求最长上升子序列

法一：二分

int LIS(){
    int b[MAXN], top = 0, a[MAXN];
    b[0] = -1;
    for(int i = 1; i <= n; i++){
        if(a[i] > b[top]){
            top++, b[top] = a[i];
        }else{
            int l = 1, r = top;
            while(l < r){             // 二分，O(log n)
                int u = (l + r) >> 1;
                if(a[i] > b[u]){
                    l = u + 1;
                }else{
                    r = u - 1;
                }
            }
            b[l] = a[i];
        }
    }
    return top;
}

法二：线段树

略