描述
Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比赛开始后，它们同时向x轴正方向移动。
假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？
输入
第一行1个整数N。
第二行为N 个非负整数，按从前到后的顺序给出每个人的跑步速度。
对于50%的数据，2<=N<=1000。
对于100%的数据，2<=N<=100000。
输出
一个整数，表示有多少对参赛者之间发生赶超事件。
分析：求数组的逆序数对个数；采用归并算法，分而治之，局部调整后的逆序对与原先的保持一致，因此在调整时计数即可。
#include<iostream>
#define N 100002
int a[N]={0},t[N]={0};
long long c=0;
void merge(int l,int m,int r){
int i=l,j=m+1,k=l;
while(i<=m&&j<=r)
if(a[i]>a[j])
t[k++]=a[i++];
else {
t[k++]=a[j++];
c+=1+m-i;
}
while(i<=m)t[k++]=a[i++];
while(j<=r)t[k++]=a[j++];
for(i=l;i<=r;++i)a[i]=t[i];
}
void divide(int l,int r){
int m;
if(r>l){
m=(r+l)/2;
divide(l,m);
divide(m+1,r);
merge(l,m,r);
}
}
int main(){
int n,i=0;
std::cin>>n;
while(i<n)std::cin>>a[i++];
divide(0,n-1);
std::cout<<c;
}
