1. 逆序數(shù)
所謂逆序數(shù)，就是指一個(gè)序列S[i]，統(tǒng)計(jì)處于序列的每個(gè)數(shù)的比這個(gè)數(shù)大并且排在它前面的數(shù)的數(shù)目，然后對(duì)于所有數(shù)，把這個(gè)數(shù)目加起來(lái)求和就是了。
比如 4 3 1 2
4第一個(gè)，所以數(shù)目為0
3的前面是4，大于3的數(shù)目為1
1的前面是4 3 ，大于1的數(shù)目為2
2的前面是4 3 1，大于2的數(shù)目為2
所以逆序數(shù)為1+2+2 = 5
求逆序數(shù)的兩種方法
常規(guī)方法是按照逆序數(shù)的規(guī)則做，結(jié)果復(fù)雜度是O(n*n)，一般來(lái)說(shuō)，有兩種快速的求逆序數(shù)的方法
分別是歸并排序和樹(shù)狀數(shù)組法
2. 歸并排序
歸并排序是源于分而治之思想，詳細(xì)的過(guò)程可以查閱其他資料，總體思想是劃分一半，各自排好序后將兩個(gè)有序序列合并起來(lái)。
如何修改歸并排序求逆序數(shù)?
首先我們假設(shè)兩個(gè)有序序列 a[i]和b[i]，當(dāng)合并時(shí)：
由于a[i]已是有序，所以對(duì)于a[i]的各個(gè)元素來(lái)說(shuō)，排在它前面且比它大的數(shù)目都是0
當(dāng)b[i]中含有比a[i]小的元素時(shí)，我們必然將b[i]元素插到前面，那么就是說(shuō)，在b[i]原先位置到該插的位置中，所有數(shù)都比b[i]大且排在它前面
所以這是b[i]的數(shù)目為新插入位置newPos - 原來(lái)位置oldPos
那么對(duì)于一半的序列又怎么做呢？我們知道，歸并排序會(huì)繼續(xù)向下遞歸，而遞歸完成返回后將是兩組有序的序列，并且拿到局部的逆序數(shù)，
所以在Merge函數(shù)中添加這一計(jì)數(shù)操作即可
代碼示例如下：
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. 樹(shù)狀數(shù)組
求逆序數(shù)的另外一種方法是使用樹(shù)狀數(shù)組
對(duì)于小數(shù)據(jù)，可以直接插入樹(shù)狀數(shù)組，對(duì)于大數(shù)據(jù)，則需要離散化，所謂離散化，就是將
100 200 300 400 500 ---> 1 2 3 4 5
這里主要利用樹(shù)狀數(shù)組解決計(jì)數(shù)問(wèn)題。
首先按順序把序列a[i]每個(gè)數(shù)插入到樹(shù)狀數(shù)組中，插入的內(nèi)容是1，表示放了一個(gè)數(shù)到樹(shù)狀數(shù)組中。
然后使用sum操作獲取當(dāng)前比a[i]小的數(shù)，那么當(dāng)前i - sum則表示當(dāng)前比a[i]大的數(shù)，如此反復(fù)直到所有數(shù)都統(tǒng)計(jì)完，
比如
4 3 1 2
i = 1 : 插入 4 : update(4,1)，sum(4)返回1，那么當(dāng)前比4大的為 i - 1 = 0;
i = 2 : 插入 3 : update(3,1)，sum(3)返回1，那么當(dāng)前比3大的為 i - 1 = 1;
i = 3 : 插入 1 : update(1,1)，sum(1)返回1，那么當(dāng)前比1大的為 i - 1 = 2;
i = 4 : 插入 2 : update(2,1)，sum(2)返回2，那么當(dāng)前比2大的為 i - 2 = 2;
過(guò)程很明了，所以逆序數(shù)為1+2+2=5
代碼示例如下：
//樹(shù)狀數(shù)組
__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;
}
//求逆序數(shù)
__int64 ret = 0;
for (__int64 i = 0; i < k; ++i)
{
update(a[i],1);
ret += (i+1) - sum(a[i]);
}