【POJ2299】Ultra-QuickSort（逆序对，归并排序）

problem

• 多组数据，每组给你一个长为n的序列
• 求该序列的逆序对个数

solution

• 对于 i < j 且 a[i] > a[j]，称a[i]与a[j]构成逆序对。
• 归并合并比较时，对于两个指针i,j ：如果a[j] < a[i]，那么a[i~mid]都比a[j]要大，他们都会与a[j]构成逆序对，将他们加入答案即可。

codes

#include<iostream>
using namespace std;
const int maxn = 500010;
int a[maxn]; long long ans = 0;
void MergeSort(int l, int r){
    if(l >= r)return ;
    int m = l+r>>1;
    MergeSort(l,m);
    MergeSort(m+1,r);
    int i = l, j = m+1;
    int t[r-l+1], k = 0;
    while(i<=m && j<=r){
        if(a[i]<=a[j])t[k++]=a[i++];
        else{
            t[k++] = a[j++];
            ans += m-i+1;//加上剩余元素个数
        }
    }
    while(i<=m)t[k++]=a[i++];
    while(j<=r)t[k++]=a[j++];
    for(i=l, k=0; i <= r; i++,k++)a[i]=t[k];
}
int main(){
    int n;
    while(cin>>n &&n){
        ans = 0;
        for(int i = 1; i <= n; i++)cin>>a[i];
        MergeSort(1,n);
        cout<<ans<<"
";
    }
    return 0;
}