Number of Inversions

/*
Author: Mehul Chaturvedi
Talent is overrated
*/

#include <bits/stdc++.h>
using namespace std;

using ll = int;
using ld = long double;
using pll = pair<ll, ll>;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define vll vector<long long>
#define vvll vector<vector<ll>>
#define vset(v, n, val) \
    v.clear();          \
    v.resize(n, val)
#define INF 4557430888798830399ll
#define fr(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define frr(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define trav(a, x) for (auto &a : x)
#define fil(ar, val) memset(ar, val, sizeof(ar))
const ll MOD = 1e9 + 7;

/*
    At each node representin [tl,tr), I store the sorted array from tl to tr-1
    Rest is pretty trivial? Just use lower_bound
*/

class node {
    public:
    vll arr;

    node(vll val) {
        arr = val;
    }
};

vector<ll> v;
vector<node> t;
ll n, m;
ll anss;

node help(node &left, node &right) {
    vll &arr1 = left.arr;
    vll &arr2 = right.arr;

    vll arr0;
    arr0.resize(arr1.size() + arr2.size());
    merge(all(arr1), all(arr2), arr0.begin());

    node res(arr0);
    return res;
}

void build(ll start, ll tl, ll tr) {
    if (tl + 1 == tr) {
        t[start] = node({v[tl]});
        return;
    }

    ll mid = (tl + tr) / 2;
    build(2 * start + 1, tl, mid);
    build(2 * start + 2, mid, tr);

    node &left = t[2 * start + 1];
    node &right = t[2 * start + 2];

    t[start] = help(left, right);
    return;
}

ll get(ll start, ll tl, ll tr, ll l, ll r, ll num) {
    if (tl >= r || tr <= l) {
        // anss = 0;
        return 0;
    }

    if (l <= tl && r >= tr) {
        vll &temp = (t[start]).arr;
        ll anss = lower_bound(all(temp), v[l]) - temp.begin();
        return anss;
    }

    ll mid = (tl + tr) / 2;
    ll left = get(2 * start + 1, tl, mid, l, r, num);
    ll right = get(2 * start + 2, mid, tr, l, r, num);
    ll ans = left+right;

    return ans;
}

vector<int> solve(vector<int> &nums) {
    t.clear();
    n = nums.size();
    if (n == 0) return {};

    v = nums;
    t.resize(4 * n, node({}));

    build(0, 0, n);
    ll q = nums.size();

    vector<int> ress;
    ll l = 0;
    while (q--) {
        auto temp = get(0, 0, n, l, n, v[l]);
        l++;
        ress.push_back(temp);
    }

    return ress;
}

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        return solve(nums);
    }
};