solution.md

# 计算右侧小于当前元素的个数

<p>给你`一个整数数组 <code>nums</code><em> </em>，按要求返回一个新数组&nbsp;<code>counts</code><em> </em>。数组 <code>counts</code> 有该性质： <code>counts[i]</code> 的值是&nbsp; <code>nums[i]</code> 右侧小于&nbsp;<code>nums[i]</code> 的元素的数量。</p>

<p>&nbsp;</p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>nums = [5,2,6,1]
<strong>输出：</strong><code>[2,1,1,0] 
<strong>解释：</strong></code>
5 的右侧有 <strong>2 </strong>个更小的元素 (2 和 1)
2 的右侧仅有 <strong>1 </strong>个更小的元素 (1)
6 的右侧有 <strong>1 </strong>个更小的元素 (1)
1 的右侧有 <strong>0 </strong>个更小的元素
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>nums = [-1]
<strong>输出：</strong>[0]
</pre>

<p><strong>示例 3：</strong></p>

<pre>
<strong>输入：</strong>nums = [-1,-1]
<strong>输出：</strong>[0,0]
</pre>

<p>&nbsp;</p>

<p><strong>提示：</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>

<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    vector<int> res;
    vector<int> nums = {5, 2, 6, 1};
    res = sol.countSmaller(nums);
    for (auto i : res)
        cout << i << " ";
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int lowbit(int x)
    {
        return (int)x & (-1 * x);
    }
    int getSum(int x, vector<int> &c)
    {
        int sum = 0;
        for (int i = x; i > 0; i -= lowbit(i))
        {
            sum += c[i];
        }
        return sum;
    }

    void update(vector<int> &c, int x, int v)
    {
        for (int i = x; i < c.size(); i += lowbit(i))
        {
            c[i] += v;
        }
    }

    vector<int> countSmaller(vector<int> &nums)
    {
        vector<int> count;
        set<int> ss;
        for (auto t : nums)
        {
            ss.insert(t);
        }
        unordered_map<int, int> m;
        int n = ss.size();
        auto it = ss.begin();
        for (int i = 1; i <= n; i++)
        {

            it++;
            m[*it] = i;
        }
        vector<int> sum(n + 1, 0);
        for (auto it = nums.rbegin(); it != nums.rend(); it++)
        {
            int res = 0;
            int idx = m[*it];
            if (idx > 1)
            {
                res = getSum(idx - 1, sum);
            }
            update(sum, m[*it], 1);
            count.push_back(res);
        }
        reverse(count.begin(), count.end());
        return count;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    vector<int> countSmaller(vector<int> &nums)
    {
        vector<int> res(nums.size(), 0);
        vector<int> indexs(nums.size(), 0);
        for (int i = 0; i < indexs.size(); i++)
        {
            indexs[i] = i;
        }
        vector<int> tempindexs(indexs.size(), 0);
        mergeSort(nums, indexs, tempindexs, res, 0, nums.size() - 1);
        return res;
    }
    void mergeSort(vector<int> &nums, vector<int> &indexs, vector<int> &tempindexs, vector<int> &res, int left, int right)
    {
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, indexs, tempindexs, res, left, mid);
        mergeSort(nums, indexs, tempindexs, res, mid + 1, right);
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right)
        {
            if (nums[indexs[i]] > nums[indexs[j]])
            {
                for (int k = i; k <= mid; k++)
                {
                    res[indexs[k]]++;
                }
                tempindexs[t++] = indexs[j++];
            }
            else
            {
                tempindexs[t++] = indexs[i++];
            }
        }
        while (i <= mid)
        {
            tempindexs[t++] = indexs[i++];
        }
        while (j <= right)
        {
            tempindexs[t++] = indexs[j++];
        }
        t = 0;
        while (left <= right)
        {
            indexs[left++] = tempindexs[t++];
        }
    }
};
```

### B

```cpp
struct BSTNode
{
    int val;
    int count;
    BSTNode *left;
    BSTNode *right;
    BSTNode(int x) : val(x), left(NULL), right(NULL), count(0) {}
};

void BST_insert(BSTNode *node, BSTNode *insert_node, int &count_small)
{
    if (node->val >= insert_node->val)
    {

        node->count++;
        if (node->left)
            BST_insert(node->left, insert_node, count_small);
        else
            node->left = insert_node;
    }
    else
    {
        count_small += node->count + 1;
        if (node->right)
            BST_insert(node->right, insert_node, count_small);
        else
            node->right = insert_node;
    }
}

class Solution
{
public:
    vector<int> countSmaller(vector<int> &nums)
    {
        int n = nums.size();
        if (!n)
            return {};
        vector<int> count;
        count.push_back(0);
        BSTNode *node = new BSTNode(nums[n - 1]);
        int count_small;
        for (int i = 1; i < n; ++i)
        {
            count_small = 0;
            BST_insert(node, new BSTNode(nums[n - i - 1]), count_small);
            count.push_back(count_small);
        }

        delete node;
        reverse(count.begin(), count.end());
        return count;
    }
};
```

### C

```cpp
class Solution
{
public:
    vector<int> help;
    vector<int> countSmaller(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 0)
            return vector<int>();
        vector<int> res(n, 0);
        for (int i = n - 1; i >= 0; --i)
        {
            auto it = lower_bound(help.begin(), help.end(), nums[i]);
            res[i] = it - help.begin();
            help.insert(it, nums[i]);
        }
        return res;
    }
};
```