14003번: 가장 긴 증가하는 부분 수열 5

https://www.acmicpc.net/problem/14003

$O(n\lg n)$

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e6;
int n, a[MXN + 1], dp[MXN + 1], idx[MXN + 1], fr[MXN + 1];
void f(int h) {
    if (!h) return;
    f(fr[h]);
    printf("%d ", a[h]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e9;
        int p = lower_bound(dp + 1, dp + 1 + i, a[i]) - dp;
        dp[p] = a[i];
        idx[p] = i;
        fr[i] = idx[p - 1];
    }
    int sz = lower_bound(dp + 1, dp + 1 + n, 1e9) - dp - 1;
    printf("%d\n", sz);
    f(idx[sz]);
    return 0;
}