solution.md

# 翻转对

<p>给定一个数组&nbsp;<code>nums</code>&nbsp;，如果&nbsp;<code>i &lt; j</code>&nbsp;且&nbsp;<code>nums[i] &gt; 2*nums[j]</code>&nbsp;我们就将&nbsp;<code>(i, j)</code>&nbsp;称作一个<strong><em>重要翻转对</em></strong>。</p>

<p>你需要返回给定数组中的重要翻转对的数量。</p>

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

<pre>
<strong>输入</strong>: [1,3,2,3,1]
<strong>输出</strong>: 2
</pre>

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

<pre>
<strong>输入</strong>: [2,4,3,5,1]
<strong>输出</strong>: 3
</pre>

<p><strong>注意:</strong></p>

<ol>
	<li>给定数组的长度不会超过<code>50000</code>。</li>
	<li>输入数组中的所有数字都在32位整数的表示范围内。</li>
</ol>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

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

### after

```cpp
int main()
{
    Solution sol;
    int res;
    vector<int> nums = {1, 3, 2, 3, 1};
    res = sol.reversePairs(nums);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int lowbit(int x)
    {
        return (int)x & 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;
        }
    }

    int reversePairs(vector<int> &nums)
    {
        int maxN = (INT_MAX) / 2, minN = (INT_MIN) / 2;
        set<int> ss;
        for (auto t : nums)
        {
            ss.insert(t);
            if (t <= maxN && t >= minN)
                ss.insert(t * 2);
        }
        unordered_map<int, int> m;
        int n = ss.size();
        auto it = ss.begin();
        for (int i = 1; i <= n; i++)
        {
            m[*it] = i;
            it++;
        }
        vector<int> sum(n + 1, 0);
        int res = 0;
        for (auto t : nums)
        {
            if (t < minN)
                res += getSum(n, sum);
            else if (t < maxN)
            {
                int idx = m[2 * t];
                res += (getSum(n, sum) - getSum(idx, sum));
            }
            update(sum, m[t], 1);
        }
        return res;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int cnt = 0;
    vector<int> tmp;
    void merge(vector<int> &nums, int beg, int mid, int end)
    {
        int i = beg, j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end)
        {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        while (i <= mid)
            tmp[k++] = nums[i++];
        while (j <= end)
            tmp[k++] = nums[j++];
        copy(tmp.begin(), tmp.begin() + k, nums.begin() + beg);
    }
    void merge_sort(vector<int> &nums, int beg, int end)
    {
        if (beg >= end)
            return;
        int mid = beg + (end - beg) / 2;
        merge_sort(nums, beg, mid);
        merge_sort(nums, mid + 1, end);

        int i = beg, j = mid + 1;
        while (j <= end)
        {
            while (i <= mid && long(nums[i]) <= 2 * long(nums[j]))
                ++i;
            cnt += mid - i + 1;
            ++j;
        }
        if (nums[mid] <= nums[mid + 1])
            return;
        merge(nums, beg, mid, end);
    }
    int reversePairs(vector<int> &nums)
    {
        int n = nums.size();
        tmp = vector<int>(n);
        merge_sort(nums, 0, n - 1);
        return cnt;
    }
};
```

### B

```cpp
class Solution
{
public:
    int mergeSort(vector<int> &nums, int l, int r)
    {
        if (l >= r)
            return 0;
        int res = 0, mid = (l + r) / 2;
        res += mergeSort(nums, l, mid);
        res += mergeSort(nums, mid + 1, r);
        int tl = l, tm = mid, tr = mid + 1;
        while (tl <= mid && tr <= r)
        {
            if ((long)nums[tl] > 2 * (long)nums[tr])
            {
                res += mid - tl + 1;
                ++tr;
            }
            else
            {
                ++tl;
            }
        }
        vector<int> tmp(r - l + 1);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j])
            {
                tmp[k++] = nums[i++];
            }
            else
                tmp[k++] = nums[j++];
        }
        while (i <= mid)
            tmp[k++] = nums[i++];
        while (j <= r)
            tmp[k++] = nums[j++];
        for (int i = l; i <= r; i++)
        {
            nums[i] = tmp[i - l];
        }
        return res;
    }
    int reversePairs(vector<int> &nums)
    {
        return mergeSort(nums, 0, nums.size() - 1);
    }
};
```

### C

```cpp
class Solution
{
public:
    int cnt = 0;
    int reversePairs(vector<int> &nums)
    {
        int n = nums.size();
        for (int i = 0; i < n - 1; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (long(nums[i]) > 2 * long(nums[j]))
                    ++cnt;
            }
        }
        return cnt;
    }
};

```