<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<vector<int>>seg; 

    

    vector<int> combine(vector<int>& a , vector<int>& b )

    {

        int n = a.size() ; 

        int m = b.size() ; 

        

        vector<int>ans(n+m)   ;

        

        int l =0 , r= 0 , index= 0; 

        while(l<n && r<m )

        {

            if(a[l]<=b[r])

            {

                ans[index++] = a[l++] ;

            }

            else

                ans[index++] = b[r++] ; 

        }

        while(l<n)

            ans[index++] = a[l++]; 

        while(r<m)

            ans[index++] = b[r++] ;

        

        return ans ; 

    }

    

    void build(int ind , int low ,int high , vector<int>& nums)

    {

        if(low==high)

        {

            seg[ind] = {nums[low]} ; 

            return  ; 

        }

        int mid= (low+high)/2 ;

        build(2*ind+1 , low , mid , nums); 

        build(2*ind+2, mid+1 , high , nums ) ; 

        

        seg[ind]= combine(seg[2*ind+1]  , seg[2*ind+2]) ; 

    } 

    

    int query(int ind  , int low, int high , int l , int r ,int val  )

    {

      if(r<low || high<l)return 0 ; 

        

        if(low>=l && high<=r)

       {

            auto it =  lower_bound(seg[ind].begin() , seg[ind].end() , val ) ;

            if(it == seg[ind].begin())

                return 0 ; 

            int res = it - seg[ind].begin();  

            return res  ; 

        }

            

            int mid= (low+high)/2 ;

     int left =query(2*ind+1 , low, mid , l, r , val ); 

      int right =   query(2*ind+2 ,  mid+1 , high , l ,r , val ); 

        

        return left+right ; 

    }

    

    

    

    vector<int> countSmaller(vector<int>& nums) {

       vector<int>ans ;  

        int n = nums.size() ; 

        seg.resize(4*n+1 ); 

        build(0 , 0 , n-1 , nums ); 

        ans.push_back(0); 

        for(int i = n-2 ; i>=0 ; i-- )

        {

            ans.push_back(query(0 , 0 , n-1 , i+1 , n-1 , nums[i] ));  

        }

        reverse(ans.begin() , ans.end()) ; 

        return ans ; 

    }

};
        
    

290156