最長上昇サブシーケンスnlogn


fiはi長の上昇サブシーケンスの最小末尾要素値を表す貪欲な方法で,現在の末尾値より小さい要素にアクセスするたびに,置換可能な位置を2分前に探す.
#include 
#include 
#include 
#include 
using namespace std;
#define debug(x) cerr << #x << "=" << x << endl;
const int MAXN = 100000 + 10;
int f[MAXN],n,a[MAXN],vis[MAXN];
int q,fa[MAXN],last[MAXN],depth[MAXN],len;
int find(int x) {
    int l=1, r=len;
    int ans;
    while(l<=r) {
        int mid = l+r>>1;
        if(f[mid] > x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
    }
    f[1] = a[1];
    len = 1;
    for(int i=2; i<=n; i++) {
        if(a[i] > f[len]) f[++len] = a[i];
        else {
            int temp = find(a[i]);
            f[temp] = a[i];
        } 
    }
    cout << len;
    return 0;
}