手写二分

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 100010;
int len = -1;
int a[N];

int main() {

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (r == -1) a[++len] = x;
        else if (a[r] > x) a[r] = x;
        else a[++len] = x;
    }

    cout << len + 1 << endl;

    return 0;
}

lower_bound()

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> v;

int main() {

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        auto it = lower_bound(v.begin(), v.end(), x);

        if (it == v.end()) v.push_back(x);
        else *it = x;
    }

    cout << v.size() << endl;
    return 0;
}