树状数组万岁

说到逆序对我就想到树状数组，今年下半年中美合办的ICPC将正式开赛，我将继续扮演被巨佬吊打的角色，打铁自闭两开花，希望大家多多关注

用树状数组维护一个数字个数的序列。数据离线，倒着查询。每查一个数之前，在树状数组里查询小于这个数的有多少个数，相当于查询这个数后面的逆序对有几个。查完之后把这个数加一。复杂度$NlogN$ 。

这时候用归并排序的同学就有人说了。明明是我先来的，排序逆序对都能搞，两件开心的事情在一起....万一数字太大存不下怎么办。那可以离散化，把每个数的次序搞出来。反正逆序对只需要相对大小，不需要绝对大小

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;
    }
};