【题解】Luogu P1774 【最接近神的人_NOI导刊2010提高(02)】

这题就求个逆序对就好了,注意有重复元素,一开始想跑树状数组,发现要离散化,所以还是跑归并吧。


typedef long long int64;

const int64 MAXN = 666666;
int64 a[MAXN],b[MAXN],cnt = 0;

void merge(int l,int mid,int r){
    int i = l,j = mid + 1;
    for(int k = l;k <= r;k++){
        if(j > r || i <= mid && a[i] <= a[j]){
            b[k] = a[i++];
        }else{
            b[k] = a[j++];
            cnt += mid - i + 1;
        }
    }
    for(int k = l;k <= r;k++){
        a[k] = b[k];
    }
}

void mergeSort(int l,int r){
    int mid = (l + r) >> 1;
    if(l != r){
        mergeSort(l,mid);
        mergeSort(mid + 1,r);
        merge(l,mid,r);
    }
}

int main(){
    int64 n;
    scanf("%lld",&n);

    for(int i = 0;i < n;i++){
        scanf("%lld",&a[i]);
    }

    mergeSort(0,n - 1);

    printf("%lld\n",cnt);

    return 0;
}