在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

样例

输入：[1,2,3,4,5,6,0]

输出：6

参考答案

class Solution {
public:
    int cnt,n,c[1000000],ans;
    void add(int x){for(; x <= cnt; x += x & -x) c[x] ++;}
    int ask(int x)
    {
        int res = 0;
        for(; x; x -= x & -x) res += c[x];
        return res;
    }
    int inversePairs(vector<int>& nums) {
        set<int> st;
        unordered_map<int,int> ump;
        cnt = 0; ans = 0; n = nums.size();
        memset(c, 0, sizeof c);
        for(auto &i : nums) st.insert(i);
        for(auto it = st.begin(); it != st.end(); it++ ) ump[*it] = ++cnt;
        for(int i = nums.size() - 1; i >= 0; i--) ans += ask(ump[nums[i]] - 1), add(ump[nums[i]]);
        return ans;
    }
};