优化后的最长上升子序列代码：（1<=N<=10,0000）$O(NlogN)$
DP + 二分
参考别人的题解： 1.有模拟过程
我写的更全的关于最长上升子序列题解

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int a[N], q[N]; //q[]存所有不同长度的最长上升子序列结尾的最小值
int f[N];

int main (){
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    int len = 0; //长度开始设为0，当前长度的最大长度len，即q[]数组中实际元素的个数，开始是0
    q[0] = -2e9; //为了保证数组当中小于某个数一定是存在的，把q[0]当成哨兵

    for (int i = 0; i < n; i ++) { //枚举每一个数
        int l = 0, r = len;
        while (l < r) { //此处二分出小于某个数的最大的数（边界问题是用q[0] = -2e9解决的）
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid; //这里是l = mid 则上面一行出 “上取整” 记得 +1 
            else r = mid - 1;
        }
        len = max(len, r + 1); //更新len最大值
        q[r + 1] = a[i]; //做完后，直接把q[len]更新成a[i]
    }

    cout << len << endl;
    return 0;
}

模板1：下取整

int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid))  r = mid;
        else l = mid + 1；
    }
    return l;
}

模板2：上取整

int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid))  l = mid;
        else r = mid - 1；
    }
    return l;
}