<p>Given an integer array <code>nums</code>, return<em> an integer array </em><code>counts</code><em> where </em><code>counts[i]</code><em> is the number of smaller elements to the right of </em><code>nums[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,6,1]
<strong>Output:</strong> [2,1,1,0]
<strong>Explanation:</strong>
To the right of 5 there are <b>2</b> smaller elements (2 and 1).
To the right of 2 there is only <b>1</b> smaller element (1).
To the right of 6 there is <b>1</b> smaller element (1).
To the right of 1 there is <b>0</b> smaller element.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1]
<strong>Output:</strong> [0]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,-1]
<strong>Output:</strong> [0,0]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

#include <bits/stdtr1c++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

struct Treap{
    int len;
    const int ADD = 1000010;
    const int MAXVAL = 1000000010;
    unordered_map <long long, int> mp; // Change to int if only int in treap
    tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> T;

    Treap(){
        len = 0;
        T.clear(), mp.clear();
    }

    inline void clear(){
        len = 0;
        T.clear(), mp.clear();
    }

    inline void insert(long long x){
        len++, x += MAXVAL;
        int c = mp[x]++;
        T.insert((x * ADD) + c);
    }

    inline void erase(long long x){
        x += MAXVAL;
        int c = mp[x];
        if (c){
            c--, mp[x]--, len--;
            T.erase((x * ADD) + c);
        }
    }

    // 0-based index, returns the K'th element in the treap, -1 if none exists
    inline long long kth(int k){
        k++;    // for 0-based indexing
        if (k < 1 || k > len) return -1;
        auto it = T.find_by_order(--k);
        return ((*it) / ADD) - MAXVAL;
    }

    // Count of values smaller than x in treap
    inline int count_smaller(long long x){
        x += MAXVAL;
        int c = mp[--x];
        return (T.order_of_key((x * ADD) + c));
    }

    // Count of values greater than x in treap
    inline int count_greater(long long x){
        x += MAXVAL;
        int c = mp[x];
        return len - T.order_of_key((x * ADD) + c);
    }

    // Number of elements in treap
    inline int size(){
        return len;
    }
};

#pragma GCC optimize (-O3, -flto, -ffast-math, -march=native, -mtune=native)

class Solution {
public:
    vector<int> countSmaller(vector<int>& a){
        Treap A;
        vector<int> ans;
        A.insert(a.back());   ans.push_back(0);   a.pop_back();
        while(!a.empty()){
            A.insert(a.back());
            ans.push_back(A.count_smaller(a.back()));
            a.pop_back();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
200268