Problem Setting

Given a sequence of integers with a length n,compute the number of reverse pairs in the sequence.

Reverse Pair

For the i-th and j-th 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
2
number of integers
n number sequence

e.g.

1
2
6
2 3 4 5 6 1

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 assume i<j), we are supposed to select q[j] as the next element in the sorted array. At the same time, it is worth noting that we have found mid-i+1 reverse pairs. Because all of the elements, from q[i] to q[mid], form reverse pairs with q[j].
  • If the input number is large, we’d better use long long for the count variable.

My Solution

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
32
33
34
35
36
#include<iostream>
using namespace std;
const int N = 100010;
int q[N], tmp[N];
long long int count = 0; //use long long int for large number(64 bit)

//can use bubble sort and tree instead
void merge_sort(int q[], int l, int r){
if (l >= r) return; // recursion base
int mid = l + r >> 1; // decide the central position in current array.
merge_sort(q, l, mid);
merge_sort(q, mid+1, r);
int i = l, j = mid + 1;
int k = 0;
// double point traversal and add count for reverse pairs
while (i <= mid && j <= r){
if (q[i] > q[j]) {
count += mid - i + 1;
tmp[k++] = q[j++]
};
else tmp[k++] = q[i++];
}
while (i <= mid) tmp[k++] = q[i++]; // the remaining array
while (j <= r) tmp[k++] = q[j++];
for (int i = l, j=0; i <= r; i++,j++) q[i] = tmp[j]; //copy back
};


int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &q[i]);
merge_sort(q, 0, n-1);
cout << count << endl;
return 0;
}