HDU 1394 Minimum Inversion Number

http://acm.hdu.edu.cn/showproblem.php?pid=1394

求最小逆序数，逆序数的树状数组求法昨天学会了，今天这题开始用个无脑O(n*n*log(n))的方法，果断超时。

其实逆序数只用求一边，每移动一次数列，逆序数增加num[i]-1个，对应减少n-num[i]个，递推即可。

#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
int n;
int tree[5001],num[5001];
int lowbit(int i){
    return i&(-i);
}
void update(int x,int val)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tree[i]+=val;
}
int Sum(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i))
        sum+=tree[i];
    return sum;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            num[i]++;
        }
        int ans=0;
        memset(tree,0,sizeof(tree));
         for(int i=1;i<=n;i++)
        {
             update(num[i],1);
               ans+=i-Sum(num[i]);
         }
         int minx=ans;
         for(int i=n;i>1;i--)
         {
            minx+=num[i]-1-(n-num[i]);
            if(ans>minx)ans=minx;
        }
        printf("%d\n",ans);
    }
    return 0;
}