[CSES] Increasing Subsequence

#define opll tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define oll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>

const ll N = 2e5 + 11;
ll tr[4 * N], a[N];
ll pull(ll l, ll r)
{
    ll p = max(l, r); // operation
    return p;
}
void build(ll node, ll l, ll r)
{
    if (l == r)
        tr[node] = a[l];
    else
    {
        ll mid = l + (r - l) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);

        tr[node] = pull(tr[node * 2], tr[node * 2 + 1]);
    }
}
void update(ll node, ll l, ll r, ll index, ll val)
{
    if (index > r || index < l)
        return;
    if (l == r)
        a[index] = val, tr[node] = val; // update operation
    else
    {
        ll mid = l + (r - l) / 2;
        update(node * 2, l, mid, index, val);
        update(node * 2 + 1, mid + 1, r, index, val);

        tr[node] = pull(tr[node * 2], tr[node * 2 + 1]);
    }
}
ll query(ll node, ll l, ll r, ll start, ll end)
{
    if (end < l || start > r)
        return -inf; // operation (inf , -inf , 0 ...)
    else if (start <= l && end >= r)
        return tr[node];
    else
    {
        ll mid = l + (r - l) / 2;
        ll p1 = query(2 * node, l, mid, start, end);
        ll p2 = query(2 * node + 1, mid + 1, r, start, end);

        return pull(p1, p2); // operation
    }
}
// build(1,0,n-1) .... query(1,0,n-1,l,r) .... update(1,0,n-1,x,a[x])

void solve()
{
    ll n;
    cin >> n;

    vll b(n);
    rep(i, n) cin >> b[i];

    vll dp(n + 1, 0LL);
    dp[0] = 1;

    map<ll, ll> mp;
    rep(i, n)
        mp[b[i]]++;

    ll id = 0;
    for (auto &x : mp)
        x.s = id++;

    a[mp[b[0]]] = 1;
    build(1, 0, n - 1);

    FOR(i, 1, n - 1)
    {
        dp[i] = 1;
        ll pdp = query(1, 0, n - 1, 0, mp[b[i]] - 1);
        dp[i] = max(dp[i], pdp + 1);
        update(1, 0, n - 1, mp[b[i]], dp[i]);
    }

    ll ans = 0LL;
    rep(i, n) ans = max(ans, dp[i]);
    cout << ans << "\n";
}