题目

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,

Ultra-QuickSort produces the output
0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

题解

逆序数问题

采用归并排序的方法来将时间复杂度从O(n²)到O(nlogn)

要特别注意，由于数据非常大，因此最坏情况下答案是超出int范围的，要使用long long保存

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)

const int maxn = 500005;
int a[maxn];

long long ans;

//将已经排好序的a[l]~a[mid] a[mid+1]~a[r]拼合起来
void merge(int a[],int l,int mid,int r) {
    int pos1 = l;//左侧的指针
    int pos2 = mid + 1;//右侧的指针
    int *temp = new int[r - l + 1];
    int pos = 0;//临时数组的指针
    while(pos1 <= mid || pos2 <= r) {
        if(pos1 > mid) {
            temp[pos++] = a[pos2++];
        }
        if(pos2 > r) {
            temp[pos++] = a[pos1++];
        }
        if(pos1 <= mid&&pos2 <= r) {
            if(a[pos1] <= a[pos2]) {
                temp[pos++] = a[pos1++];
            } else {
                temp[pos++] = a[pos2++];
                ans += mid - pos1 + 1;//交换
            }
        }
    }
    for(int i = 0;i <= r - l;i++)
        a[l + i] = temp[i];
}

//归并排序 对a[l]~a[r]排序
void mergesort(int a[],int l,int r) {
    if(l<r) {
        int mid = (l + r) / 2;
        mergesort(a,l,mid);
        mergesort(a,mid + 1,r);
        merge(a,l,mid,r);
    }
}

bool Do() {
    int n;
    if(scanf("%d",&n),n == 0)
        return false;

    REP(n)
        scanf("%d",&a[o]);

    ans = 0;
    mergesort(a,0,n - 1);
    printf("%lld\n",ans);
    /*REP(n)
    printf("%d ",a[o]);
    printf("\n");*/

    return true;
}

int main() {
    while(Do());
    return 0;
}