<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>

static const int speedup = []{ios::sync_with_stdio(0); cin.tie(0); return 0;}();

class Solution {
public:
    struct CountSmaller {
        int value;
        int pos;
        int count = 0;
    };

    using iterator = std::vector<CountSmaller>::iterator;

    void merge(iterator left1, iterator right1, iterator left2, iterator right2, iterator dest) {
        iterator begin = dest;
        iterator left  = left1;
        while (true) {
            iterator right;
            if (left1 != right1 && left2 != right2)
                right = left1->value <= left2->value ? left1++ : left2++;
            else if (left1 != right1)
                right = left1++;
            else if (left2 != right2)
                right = left2++;
            else
                break;
            right->count = std::max(right->count, static_cast<int>(right->count + begin - dest - (right - left)));
            *begin++ = *right;
        }
    }

    void merge_sort(iterator left, iterator right) {
        std::ptrdiff_t diff = right - left;
        if (diff < 2)
            return;
        std::vector<CountSmaller> dest(diff);
        iterator mid = left + diff / 2;
        merge_sort(left, mid);
        merge_sort(mid, right);
        merge(left, mid, mid, right, dest.begin());
        std::copy(dest.begin(), dest.end(), left);
    };

    std::vector<int> countSmaller(std::vector<int>& nums) {
        std::vector<CountSmaller> smaller;
        smaller.reserve(nums.size());
        for (int i = 0; i < nums.size(); ++i)
            smaller.emplace_back(nums[i], i, 0);
        merge_sort(smaller.begin(), smaller.end());
        std::vector<int> ans(nums.size());
        for (auto const& count : smaller)
            ans[count.pos] = count.count;
        return ans;
    }
};
279581