Sort Numbers with Swap III

uuuouou

从题目上看，只能交换相邻的两个，这是bubble sort的规则，很容易想到直接bubble sort一次统计swap的次数即可，这样做是O(N^2)的，由于题目中N最大是10万，就会超时了。我们回过头来看bubble sort，它什么时候会进行swap呢，就是发现a【i】 > a[i+1]的时候，swap两者之后如果发现还有a[i+1] > a[i+2]，则继续swap。我们可以发现，对于一个数a【i】，a[i+1]~a[n-1]有多少个比它小的，即有多少个逆序对，我们就要swap多少次a【i】。更重要的是，将a【i】 swap到位之后，a[i-1]的逆序对个数并不受影响，即该对a[i-1] swap几次还是要继续swap几次。
从而问题转化为对每个a【i】统计a[i+1]~a[n-1]有多少个比自己小的数，利用树状数组便可以在O(NlogN)的时间复杂度下完成：class Solution {
private:
        static const int MAX_N = 100000;
        typedef long long LL;
        LL c[MAX_N + 5];
       
        LL sum(int x){
                LL s = 0;
                for(; x; x -= x&-x) s += c[x];
                return s;
        }
        void add(int x, int n){
                for(; x <= n; x += x&-x) ++c[x];
        }
public:
        long long sortWithSwap(vector<int> &a) {
                int n = a.size();
                if(n < 2) return 0;
               
                memset(c, 0, (n+1)*sizeof(LL));
                LL tot = 0;
                for(int i = n-1; i > -1; --i){
                        tot += sum(a【i】);
                        add(a【i】 + 1, n);
                }
                return tot;
        }
};