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

One number, the answer.

*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);
}