9201.Freda的越野跑

描述
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;
}