再见逆序数

poj-2299-Ultra-QuickSort

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

大意：给出长度为n的序列，每次只能交换相邻的两个元素，问至少要交换几次才使得该序列为递增序列。
思路：样例少的话直接冒泡统计下交换次数就行了，但这个题就不行了，可以换个方向考虑，逆序数也是交换两个数的位置并排序，可以想到统计下逆序数的个数就行了。

#include<stdio.h>
typedef long long ll;
int a[500010],ans[500010];
int n,i,j,k;

ll solve(int l,int r)
{
    int mid = (l + r) >> 1;
    if(l == r)
        return 0;
    ll num = 0;
    num += solve(l , mid);
    num += solve(mid + 1, r);
    for(i = l, j = mid + 1, k = 0; i <= mid || j <=r; k++)
    {
        if(i > mid) ans[k] = a[j++];
        else if(j > r) ans[k] = a[i++];
        else if(a[i] <= a[j]) ans[k] = a[i++];
        else{

            ans[k] = a[j++];
            num += mid - i + 1;
        }
    }
    for(i = 0; i <= r-l; i++)
        a[i+l] = ans[i];
    return num;
}

int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        for(i = 0; i < n; i++)
            scanf("%d",&a[i]);
        printf("%lld\n",solve(0,n-1));
    }
    return 0;
 }