Inversion Number

Description
There is a permutation P with n integers from 1 to n. You have to calculate its inversion number, which is the number of pairs of Pi and Pj satisfying the following conditions: iPj. 
Input
 The input may contain several test cases.
In each test case, the first line contains a positive integer n (n<=100000) indicating the number of elements in P. The following n lines contain n integers making the permutation P.
Input is terminated by EOF.
Output
 For each test case, output a line containing the inversion number.
テーマの解釈:1つの無秩序な配列に対して、逆順序の対の個数を解く
問題解決の考え方:2つのforループを使えばこの問題を解決できると言っていますが、forループを使うとタイムアウトになります.従って,分治アルゴリズムを用いて,1つの大きな配列を解く逆シーケンスをいくつかの小さな配列を解く逆シーケンスに変える.このアルゴリズムは以前の最近の隣接点対の解とよく似ている.問題を解く手順は以下の通りです.
(1)再帰的に配列を分割できないまで分割する.
(2)隣接する2つの配列について逆シーケンスを解く
(3)求解完逆序数の2つの数のグループを並べ替える.
(4)連結後の配列についても同様の操作を行う.
後記:本来はnewとdeleteを使ってダイナミックメモリ割り当てをしようと思っていたのですが、Sicilyは通れず、なぜか~

#include 
#include 
using namespace std;
int P[100005];
int element_num;
long long result;    //            long long ，     。
int getIndex(int *arr, int begin, int end, int target){
    int mid = 0;
    while (begin <= end) {
        mid = (begin + end) /2;
        if (target < arr[mid]) end = mid - 1;
        else if(target > arr[mid]) begin = mid + 1;
        else return mid;
    }
    return begin;
}
void sortmerge(int *arr, int begin, int mid, int end){
    int i, j;
    int l1 = mid - begin + 1;
    int l2 = end - mid;
    int *L = (int*)malloc(sizeof(int)*l1);   //             
    int *R = (int*)malloc(sizeof(int)*l2);   //             
    for (i = 0; i < l1; i++) {
        L[i] = arr[i+begin];
    }
    for (i = 0; i < l2; i++) {
        R[i] = arr[mid+1+i];
    }
    for(i = 0; i < l2; i++){
        result += (l1 - getIndex(L, 0, l1-1, R[i]));
    }
    i = j = 0;
    int k = begin;
    while (i < l1 && j < l2) {   //             
        if (L[i] < R[j]) {
            arr[k] = L[i];
            i++;
        }
        else{
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < l1) {
        arr[k] = L[i];
        k++;
        i++;
    }
    while (j < l2) {
        arr[k] = R[j];
        k++;
        j++;
    }
    free(L);
    free(R);
}
void Merge(int *arr, int begin, int end){
    if (begin < end) {
        int mid = (begin + end) / 2;
        Merge(arr, begin, mid);
        Merge(arr, mid + 1, end);
        sortmerge(arr, begin, mid, end);
    }
}
int main(){
    while (cin >> element_num) {
        for (int i = 0; i < element_num; i++) {
            cin >> P[i];
        }
        result = 0;
        Merge(P, 0, element_num-1);
        cout << result << endl;
    }
    return 0;
}