ACM归并排序求逆序对-火柴排队

http://codevs.cn/problem/3286/
这里引用ssoj官网题解：
贪心+逆序对。分析如下：
对距离公式化简得：

∑(ai-bi)2=∑(ai2-2aibi+bi2)=∑ai2+∑bi2-2∑aibi，要求∑(ai-bi)2最小，就只需要∑aibi最大即可。这里有个贪心，当 a1<a2<…<an ，b1<b2<…<bn时，∑aibi最大。

证明如下：

若存在a>b，c>d，且ac+bd<ad+bc，则a(c-d)<b(c-d)，则a<b，与a>b矛盾，所以若a>b，c>d，则ac+bd>ad+bc
将此式子进行推广：
当a1<a2<a3<…<an ，b1<b2<…<bn的情况下∑aibi最大，即∑(ai-bi)2最小。

然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列中的数等效于只移动一个序列中的数，移动的时候可以将一个火柴序列不动，只移动另外一个序列。

于是可以构造一个数组C，C[i]表示最初的第i个数应该移动到C[i]位置。于是问题转换成对C[i]数组排序，每次可以交换相邻两个数，问最少需要移动多少次的问题了，也就是求这个序列的逆序对数量的问题（这里用归并排序思想实现）。

例如：
对于数据：
4
1 3 4 2
1 7 2 4

先排序:
1 2 3 4
1 2 4 7

image.jpeg

保持序列1不动，那么：
序列2中的“1”对应序列1中的位置1；
“7”对应序列1中的位置3；
“2”对应序列1中的位置4；
“4”对应序列1中的位置2，那么重定义数组c为：

image.jpeg

这个序列：1 3 4 2 的逆序对数量是 2 ，即（3,2）和(4,2)，所以答案是 2。

#include<iostream>
#include<stdio.h>
using namespace std;
#define OK 1
#define MOD 99999997 
#define MAXSIZE 100010
typedef int Status;
typedef long long ll;
struct A
{
    int key;
    int b;
};
typedef struct
{
    A *r;
    int length;
}SqList;

Status InitList(SqList &L)
{
    L.r=new A[MAXSIZE];
    L.length=0;
    return OK;
}
void MergerSort(SqList &L,SqList &T,int low,int high);
int Partition ( SqList &L,int low,  int  high ) ;
void QSort ( SqList &L,int low,  int  high ) ;
void swap(SqList &L)
{
    for(int i=1;i<=L.length;i++)
    {
        L.r[0].key=L.r[i].key;
        L.r[i].key=L.r[i].b;
        L.r[i].b=L.r[0].key;
    }
}
long long count=0;
int main()
{
    int n;
    SqList L1,L2,L3,T;
    InitList(L1);
    InitList(L2);
    InitList(L3);
    InitList(T);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>L1.r[i].key;
        L1.r[i].b=i;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>L2.r[i].key;
        L2.r[i].b=i;
    }
    L1.length=n;
    L2.length=n;
    QSort(L1,1,L1.length);
    QSort(L2,1,L2.length);
    for(int i=1;i<=L1.length;i++)
    {
        L3.r[L2.r[i].b].b=L1.r[i].b;
    }
    L3.length=n;
    swap(L3);
    count=0;
    MergerSort(L3,T,1,L3.length);
    cout<<count<<endl;
    return 0;
}
void MergerSort(SqList &L,SqList &T,int low,int high)
{
    if(low==high)
        return ;
    else
    {
        int mid=(low+high)/2;
        MergerSort(L,T,low,mid); 
        MergerSort(L,T,mid+1,high);
        int i=low,j=mid+1,k=low;
        while(i<=mid&&j<=high)
        {
            if(L.r[i].key<=L.r[j].key)
            {
                T.r[k++]=L.r[i++];
            }
            else
            {
                T.r[k++]=L.r[j++];
                count=(count+mid-i+1)%MOD;
            }
        }
        while(i<=mid)
        {
            T.r[k++]=L.r[i++];
        }
        while(j<=high)
        {
            T.r[k++]=L.r[j++];
        }
        for(int o=low;o<=high;o++)
            L.r[o]=T.r[o];
    }
}
void QSort ( SqList &L,int low,  int  high ) 
{  if  ( low < high ) 
    {  
        int pivotloc = Partition(L, low, high );
        QSort(L,low,pivotloc-1); 
        QSort(L, pivotloc+1, high ); 
     }
}
int Partition ( SqList &L,int low,  int  high ) 
{  
    L.r[0] = L.r[low];  
    int pivotkey = L.r[low].key;
   while  ( low < high ) 
    { while ( low < high && L.r[high].key >= pivotkey )  --high;
                 L.r[low] = L.r[high];
      while ( low < high && L.r[low].key <= pivotkey )  ++low;
                 L.r[high] = L.r[low];
     }
    L.r[low]=L.r[0]; 
    return low;
}