# 11542: 【原1542】逆序对

### 题目描述

author: 金耀楠 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1542

## Description

Given n numbers, output the number of reverse pair. The reverse pair is such number pair (a,b): the position of a is smaller than b and the value of a is bigger than b.

For example, Given an array of number 9 5 1 6 2 7 3 8, there are 13 reverse pairs:

(9,5), (9,1), (9,6), (9,2), (9,7), (9,3), (9,8), (5,1), (5,2), (5,3), (6,2), (6,3), (7,3)

(This is the problem C for SEIEE-Yu Yong Data Structure 2015 Fall Exam 2)

## Input Format

Two rows, the first row is a number n.

The second rows is n numbers separated by a blank.

## Output Format

*hint: The answer is probably bigger than 2^31.

## Sample Input

``````8
9 5 1 6 2 7 3 8
``````

## Sample Output

``````13
``````

## Data Range

40%0 : n < 1000

100% : n < 300 000

## yyong119's solution

``````#include <cstdio>

using namespace std;

const int MAXN = 300000;
int a[MAXN + 10];
long num;

void mergearr(int l, int r) {

int mid = (l + r) >> 1, i = l, j = mid + 1, k = l;
int temp[MAXN + 10];
while ((i <= mid)&&(j <= r)) {
if (a[i] > a[j]) {
temp[k++] = a[j++];
num += mid - i + 1;
} else {
temp[k++] = a[i++];
}
}
while (i <= mid) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (int i = l; i <= r; i++) a[i] = temp[i];
}

void merge_sort(int l, int r) {

if (l < r) {
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
mergearr(l, r);
}
}

int main() {

int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
merge_sort(1, n);
printf("%ld\n", num);
}
``````