Problem H: Recursion / Divide and Conquer - The Number of Inversions

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $302$ 正确数量 $249$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL 排序

The Number of Inversions

For a given sequence A={a0,a1,...an−1}, the number of pairs (i,j)where ai>aj and i<j,is called the number of inversions.The number of inversions is equals to the number of swaps of Bubble Sort defined in the following program:

     bubbleSort(A)

       cnt = 0 // the number of inversions 

     for i = 0 to A.length-1 

        for j = A.length-1 downto i+1 

           if A[j] < A[j-1] 

              swap(A[j], A[j-1]) 

               cnt++

       return cnt 

For the given sequence A, print the number of inversions of A. Note that you should not use the above program, which brings Time Limit Exceeded.

In the first line, an integer n, the number of elements in A, is given. In the second line, the elements ai (i=0,1,..n−1) are given separated by space characters.
Print the number of inversions in a line.
5
3 5 2 1 4
6

1≤n≤200,000

0≤ai≤10^9

ai are all different