Luogu. P1908Reverse

For a positive integer series given, reverse sequence is in the sequencea_I > a_j and I<j The orderly right. Note that there may be duplicate numbers in the sequence.

Input Format

First line, one number, n, indicates that there is a sequence.No, no, no.Numbers.

Second lineNo, no, no.Number, indicating the given sequence. No more than 10 per number in the sequence⁹。

For 25% of data, n-2500.

For 50% of data, n≤4 x 10⁴。

For all data, n≤5 x 10⁵。

Output Format

Number of reverse-sequence pairs in the output series.

输入
6 
5 4 2 6 3 1

输出
11

Example:

Method of achievement

#include <iostream>
using namespace std;

typedef long long LL;

int n, a[5000010], b[5000010];
LL res = 0;

void reverse_pair(int l, int r){
    if(l >= r) return;
    int mid = (l + r) >> 1;
    reverse_pair(l, mid);
    reverse_pair(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++], res += mid - i + 1;

    while(i <= mid) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    for(i = l; i <= r; i++) a[i] = b[i];
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    reverse_pair(0, n - 1);
    cout << res;
    return 0;
}

of 'res + = mid - i + 1 ' : When combining two orderly arrays, if a [i]>a [j] indicates that a [i] and the elements behind it are larger than a [i] because the array is orderly. Thus, for the current a[j], it is in reverse with the remaining elements in the first half of the array.