1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
long long mergesort(int *a,int l,int r){
    if(l == r){
        return 0;
    }
    if(l + 1 == r){
        if(a[l] > a[r]){
            int tmp = a[l];
            a[l] = a[r];
            a[r] = tmp;
            return 1;
        }else{
            return 0;
        }
    }
    int mid = (r-l)/2+l;
    long long lcount = mergesort(a,l,mid);
    long long rcount = mergesort(a,mid+1,r);
    int i=l,j=mid+1;
    int *tmp = (int *)malloc((r-l+1)*sizeof(int));
    int k = 0;
    long long curcount =0;
    while(i<=mid && j <= r){
        if(a[i]<=a[j]){
            tmp[k++] = a[i++];
        }else{
            tmp[k++] = a[j++];
            curcount += mid - i +1;
        }
    }
    if(i<=mid){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX