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 <cstdio>  
const int MAXM = 100000 + 10; 
long long ans; 
int num[MAXM]; 
void merge(const int head, const int tail)
{
    int* tmp = new int[tail - head + 1]; 
    int mid = head + (tail - head)/2; 
    int i = head, j = mid + 1; 
    int k = 0; 
    while(i <= mid && j <= tail)
    {
        if(num[i] <= num[j])
        {
            tmp[k++] = num[i++]; 
        }else
        { 
            ans += mid - i + 1; 
            tmp[k++] = num[j++]; 
        }
    }
    while(i <= mid)
    {
        tmp[k++] = num[i++]; 
    }
    while(j <= tail)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX