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

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

private:
    struct IntAndIndex {
        int value;
        int index;

        IntAndIndex( int v, int i ) : value( v ), index( i ) {};
    };

    vector<IntAndIndex> myArray;
    vector<int> changes;

    void mergeSorted( int leftStart, int rightStart, int end );
    void sortArray( int start, int end );

};

vector<int> Solution::countSmaller( vector<int>& nums )
{
    changes.clear();
    myArray.clear();
    if( nums.empty() ) {
		return vector<int>{};
	}
	changes.insert( changes.end(), nums.size(), 0 );
	for( int i = 0; i < static_cast<int>( nums.size() ); i++ ) {
		myArray.push_back( IntAndIndex( nums[i], i ) );
	}
	sortArray( 0, static_cast<int>( myArray.size() ) - 1 );
    return changes;
}

void Solution::mergeSorted( int leftStart, int rightStart, int end )
{
	assert( changes.size() == myArray.size() );
	assert( leftStart >= 0 && leftStart < static_cast<int>( myArray.size() ) );
	assert( rightStart >= 0 && rightStart < static_cast<int>( myArray.size() ) );
	assert( end >= 0 && end < static_cast<int>( myArray.size() ) );
	assert( leftStart < rightStart && rightStart <= end );

	int i = leftStart;
	int j = rightStart;
	vector<IntAndIndex> result;
    vector<int> additional( rightStart - leftStart, 0 ); 
	while( i < rightStart && j <= end ) {
		if( myArray[i].value <= myArray[j].value ) {
			result.push_back( myArray[i++] );
		} else {
			result.push_back( myArray[j++] );
            additional[i - leftStart]++;
		}
	}
    int penalty = 0;
	for( int i = 0; i < static_cast<int>( additional.size() ); i++ ) {
		penalty += additional[i];
		const int originalIndex = myArray[leftStart + i].index;
		changes[originalIndex] += penalty;
	}
	while( i < rightStart ) {
		result.push_back( myArray[i++] );
	}
	while( j <= end ) {
		result.push_back( myArray[j++] );
	}
	assert( static_cast<int>( result.size() ) == end - leftStart + 1 );
	for( int i = 0; i < static_cast<int>( result.size() ); i++ ) {
		myArray[leftStart + i] = result[i];
	}
}

void Solution::sortArray( int start, int end )
{
	assert( myArray.size() == changes.size() );
	assert( start >= 0 && start < static_cast<int>( myArray.size() ) );
	assert( end >= 0 && end < static_cast<int>( myArray.size() ) );
	assert( start <= end );

	if( start == end ) {
		return;
	}
	if( start == end - 1 ) {
		if( myArray[start].value > myArray[end].value ) {
			const int startOriginalIndex = myArray[start].index;
			changes[startOriginalIndex]++;
			swap( myArray[start], myArray[end] );
		}
		return;
	}
	const int middle = ( start + end ) / 2;
	sortArray( start, middle );
	sortArray( middle + 1, end );
	mergeSorted( start, middle + 1, end );
}

485793