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>
int arr[100005],b[100005];
long long int count,tmp;
void merge(int low,int mid,int high){
    int i,j,k;
    for(i=low;i<=high;i++)
        b[i]=arr[i];
    tmp=0;
    for(i=low,j=mid+1,k=low;i<=mid&&j<=high;){
        if(b[i]<=b[j]){
            arr[k++]=b[i++];
            count+=tmp;
        }else{
            arr[k++]=b[j++];
            tmp++;
        }
    }
    while(i<=mid){
        arr[k++]=b[i++];
        count+=tmp;
    }
    while(j<=high){
        arr[k++]=b[j++];
    }
}
void merge_sort(int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        merge_sort(low,mid);
        merge_sort(mid+1,high);
        merge(low,mid,high);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX