1. 逆序數

所謂逆序數，就是指一個序列S[i]，統計處于序列的每個數的比這個數大并且排在它前面的數的數目，然后對于所有數，把這個數目加起來求和就是了。
比如 4 3 1 2
4第一個，所以數目為0
3的前面是4，大于3的數目為1
1的前面是4 3 ，大于1的數目為2
2的前面是4 3 1，大于2的數目為2
所以逆序數為1+2+2 = 5

求逆序數的兩種方法
常規方法是按照逆序數的規則做，結果復雜度是O(n*n)，一般來說，有兩種快速的求逆序數的方法
分別是歸并排序和樹狀數組法

2. 歸并排序
歸并排序是源于分而治之思想，詳細的過程可以查閱其他資料，總體思想是劃分一半，各自排好序后將兩個有序序列合并起來。

如何修改歸并排序求逆序數?
首先我們假設兩個有序序列 a[i]和b[i]，當合并時：
由于a[i]已是有序，所以對于a[i]的各個元素來說，排在它前面且比它大的數目都是0
當b[i]中含有比a[i]小的元素時，我們必然將b[i]元素插到前面，那么就是說，在b[i]原先位置到該插的位置中，所有數都比b[i]大且排在它前面
所以這是b[i]的數目為新插入位置newPos - 原來位置oldPos

那么對于一半的序列又怎么做呢？我們知道，歸并排序會繼續向下遞歸，而遞歸完成返回后將是兩組有序的序列，并且拿到局部的逆序數，
所以在Merge函數中添加這一計數操作即可

int L[M];
int R[M];

const int Max = 1 <<30;
__int64 change = 0;

void Merge(int *data,int left,int divide,int right)
{
    int lengthL = divide - left;
    int lengthR = right - divide;
    
    for(int i = 0; i < lengthL; ++i)
    {
        L[i] = data[left + i];
    }
    for(int i = 0; i < lengthR; ++i)
    {
        R[i] = data[divide + i];
    }
    L[lengthL] = R[lengthR] = Max;
    int i = 0;
    int j = 0;
    for(int k = left; k < right; ++k)
    {
        if(L[i] <= R[j])
        {
            data[k] = L[i];
            ++i;
        }
        else 
        {
            change += divide - i - left ;
            data[k] = R[j];
            ++j;
        }
    }

}

void MergeSort(int *data,int left,int right)
{
    if(left < right -1)
    {
        int divide = (left + right)/2;
        MergeSort(data,left,divide);
        MergeSort(data,divide,right);
        Merge(data,left,divide,right);
    }
}

3. 樹狀數組
求逆序數的另外一種方法是使用樹狀數組
對于小數據，可以直接插入樹狀數組，對于大數據，則需要離散化，所謂離散化，就是將
100 200 300 400 500 ---> 1 2 3 4 5

這里主要利用樹狀數組解決計數問題。

首先按順序把序列a[i]每個數插入到樹狀數組中，插入的內容是1，表示放了一個數到樹狀數組中。
然后使用sum操作獲取當前比a[i]小的數，那么當前i - sum則表示當前比a[i]大的數，如此反復直到所有數都統計完，
比如
4 3 1 2
i = 1 : 插入 4 : update(4,1)，sum(4)返回1，那么當前比4大的為 i - 1 = 0;
i = 2 : 插入 3 : update(3,1)，sum(3)返回1，那么當前比3大的為 i - 1 = 1;
i = 3 : 插入 1 : update(1,1)，sum(1)返回1，那么當前比1大的為 i - 1 = 2;
i = 4 : 插入 2 : update(2,1)，sum(2)返回2，那么當前比2大的為 i - 2 = 2;

過程很明了，所以逆序數為1+2+2=5

代碼示例如下：

//樹狀數組
__int64 sums[1005];
int len;

inline int lowbit(int t)
{
    return t & (t^(t-1)); 
}

void update(int _x,int _value)
{
    while(_x <= len)
    {
        sums[_x] += _value;
        _x += lowbit(_x);
    }
}

__int64 sum(int _end)//get sum[1_end]
{
    __int64 ret = 0;
    while(_end > 0)
    {
        ret += sums[_end];
        _end -= lowbit(_end);
    }
    return ret;
}

//求逆序數

__int64 ret = 0;
for (__int64 i = 0; i < k; ++i)
{
    update(a[i],1);
    ret += (i+1) - sum(a[i]);
}

求逆序數的題目有：
http://poj.org/problem?id=2299
http://poj.org/problem?id=3067