LIS O(nlogn) longitud y secuencia

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#define ll long long
#define scani(x) scanf("%i", &x)
#define scanll(x) scanf("%I64d", &x)
#define scanfl(x) scanf("%f", &x)
#define scanch(x) scanf("%c", &x)
#define scans(x) scanf("%s", x);
#define printi(x) printf("%i", x);
#define printll(x) printf("%I64d", x);
#define printfl(x) printf("%f", x);
#define printch(x) printf("%c", x);
#define prints(x) printf("%s", x);
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define INFI (1 << 29)
#define INFL (1LL << 62)
#define sz(x) int(x.size())
#define forn(i, n) for (ll i = 0; i < n; i++)
#define for1(i, n) for (ll i = 1; i <= n; i++)
#define ford(i, n) for (ll i = (n - 1); i >= 0; i--)
#define fori(i, n) for (ll i = n; i >= 1; i--)
#define fore(i, l, r) for (ll i = l; i <= r; i++)

using namespace std;

ll n, v[1000000], b[1000000], LIS, ub;
vector<ll> a(1000000);

ll ceilBinario(const ll &val)
{
    ll pos = INFL, ini = 0, fin = LIS, m;

    while ((ini + 1) < fin)
    {
        m = ((ini + fin) / 2);

        if (v[a[m]] < val)
            ini = m;
        else
            fin = m, pos = min(pos, m);
    }

    if (v[a[ini]] >= val)
        pos = min(pos, ini);
    if (v[a[fin]] >= val)
        pos = min(pos, fin);

    return pos;
}

void showSubsequence()
{
    ll i = (n - 1);

    vector < ll > seq;

    while(b[i] != (-1))
    {
        seq.push_back(v[i]);

        i = b[i];
    }

    seq.push_back(v[i]);

    ford(i, sz(seq))
        printf("%I64d ", seq[i]);
    prints("\n");
}

ll longestIncreasingSubsequence()
{
    memset(b, (-1), sizeof(b));

    LIS = 0, a[0] = 0;

    for1(i, (n - 1))
    {
        if (v[i] < v[a[0]])
            a[0] = i;
        else if (v[i] > v[a[LIS]])
            a[1 + LIS++] = i, b[i] = a[LIS - 1];
        else
        {
            ub = ceilBinario(v[i]);

            a[ub] = i, b[i] = a[ub - 1];
        }
    }

    return (LIS + 1);
}

int main()
{
    scanll(n);

    forn(i, n) scanll(v[i]);

    printll(longestIncreasingSubsequence()); prints("\n");

    showSubsequence();

    return 0;
}