题目：

---

题解：

思路：归并排序的模板题，在递归处理两个升序子序列时，a[l…r] 中的左序列 a[l…mid] 和右序列 a[mid+1,r] 利用两个指针 i 和 j 在合并时，顺便进行统计逆序对个数。若 a[i]>a[j]，由于 a[l…r] 是升序的，那么 a[i…mid]之间的所有元素都会大于 a[j]，统计此时的个数为 mid-i+1 即可。

---

代码如下：

const int N = 5e5+10;
int b[N];
class Solution {
public:
    int reversePairs(vector<int>& a) {
        memset(b,0,sizeof b);
        int n=a.size();
        return merge(a,0,n-1);
    }

    int merge(vector<int>& a,int l,int r)
    {
        if(l>=r)return 0;
        // 1.确定分界点，递归处理左右两段
        int mid=(l+r)>>1;
        int res=merge(a,l,mid)+merge(a,mid+1,r);
        // 2.统计逆序对的个数，顺便合并两个升序子序列
        int i=l,j=mid+1,k=0;
        while(i<=mid||j<=r)
        {
            if(i>mid)b[k++]=a[j++];
            else if(j>r)b[k++]=a[i++];
            else{
                if(a[i]<=a[j])b[k++]=a[i++];
                else{
                    b[k++]=a[j++];
                    // 由于a[i]>a[j]，且a[l,mid]是升序的，那么a[i...mid]都会大于a[j]
                    res+=(mid-i+1);
                }
            }
        }
        // 3.还原数组a
        for(i=0;i<k;++i)a[l+i]=b[i];
        return res;
    }
};