Right Smaller Than

• Time : O(nlogn)
• Space : O(nlogn)

using namespace std;

struct Seg {
    int mi, ma, count;
    Seg *l, *r;
    Seg(vector<int>& A, int left, int right) : count(0), l(nullptr), r(nullptr) {
        mi = A[left], ma = A[right];
        if(left == right) return;
        int m = (left + right) / 2;
        l = new Seg(A, left, m);
        r = new Seg(A, m + 1, right);
    }

    ~Seg() {
        if(l) delete l;
        if(r) delete r;
    }

    int query(int s, int e) {
        if(mi > e or ma < s) return 0;
        if(s <= mi and ma <= e) return count;
        return (l ? l->query(s, e) : 0) + (r ? r->query(s, e) : 0);
    }

    void update(int n, int v) {
        if(mi <= n and n <= ma) {
            count += v;
            if(l) l->update(n, v);
            if(r) r->update(n, v);
        }
    }
};

vector<int> rightSmallerThan(vector<int> array) {
    if(array.empty()) return {};
    vector<int> sorted = array;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    Seg *seg = new Seg(sorted, 0, sorted.size() - 1);
    vector<int> res(array.size());
    for(int i = array.size() - 1; i >= 0; i--) {
        res[i] = seg->query(sorted[0], array[i] - 1);
        seg->update(array[i], 1);
    }
    return res;
}