HDU 1394ツリー配列で逆シーケンスを求める

标题:ひとつ由0..n-1からなるシーケンスは、キューの先頭の要素をキューの最後に移動するたびに、形成されたn個のシーケンスの最小逆シーケンス対数を求めることができる.
アルゴリズム:
ツリー配列から逆シーケンスペアを求める.加入元素i即把元素i为下标的a[i]値+1,从队尾到队首入队,
エンキューのたびに逆シーケンス対数+=getsum(i-1)、すなわち、下位スケールはそれより大きいが値はそれより小さい要素の個数である.
ツリー配列は下に0と表示された要素を処理できないため,各要素が入ると+1となり,対応する他のプログラムも調整される.
元のシーケンスの逆順対個数を求めた後、一番前の要素をキューの尾に移動するたびに、逆順対数は
元の逆順対数+iより大きい元素の個数-iより小さい元素の個数、0であるため..n,直接算出しやすく,minを更新するたびによい.

#include <stdio.h>
#define MAXN 10000

int c[MAXN],a[MAXN],n;

int min(int a,int b)
{
    if (a < b) return a;
    else return b;
}

int lowbit(int i)
{
    return i & -i;
}


void update(int i,int x)
{
    while (i <= n)
    {
        c[i] += x;
        i += lowbit(i);
    }
}

int getsum(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}

int main()
{
    while (scanf("%d", &n) == 1)
    {
        for (int i = 1; i <= n; i++)
            c[i] = 0;
        int sum = 0;
        for (int i = 1; i <= n; i ++)
        {
            scanf ("%d", &a[i]);
        }
        for (int i = n; i >= 1; i --)
        {
            update (a[i] + 1, 1);
            sum += getsum (a[i]);
        }
        int ans = sum;
        for (int i = 1; i <= n; i++)
        {
            sum = sum - a[i] + (n - a[i] - 1);
            ans = min(ans, sum);
        }
        printf("%d
", ans);
    }
    return 0;
}