Problem Setting
Given a sequence of integers with a length n
,compute the number of reverse pairs in the sequence.
Reverse Pair
For the ith and jth element in the sequence a
, if it meets the condition that i < j
and a[i] > a[j]
, then it is a reverse pair; otherwise it’s not.
Data Range
$1 \leq n \leq 100000$
Input format
1  number of integers 
e.g.
1  6 
Output
number of reverse order pairs, e.g.
1  5 
Analysis
 Here we use quick sort to approach this problem. The connection between this problem and the original quick sort is that when we do the sorting and
q[i] > q[j]
(we assumei<j
), we are supposed to selectq[j]
as the next element in the sorted array. At the same time, it is worth noting that we have foundmidi+1
reverse pairs. Because all of the elements, fromq[i]
toq[mid]
, form reverse pairs withq[j]
.  If the input number is large, we’d better use
long long
for the count variable.
My Solution
1 
