hdu1394Minimum Inversion Number樹狀數組求逆序對水題

//ans[i]=ans[i⑴]+(n+1)⑵*num[i]
//num[i]為輸入時的數據
//ans[i]為m=i時的逆序數
//用樹狀數組求ans[0]的逆序對
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5010;
int num[maxn];
int tree[maxn];
int lowbit(int i)
{
    return i&(-i);
}
int getsum(int i)
{
    int sum=0;
    while(i>0)
    {
        sum+=tree[i];
        i-=lowbit(i);
    }
    return sum;
}
void update(int i,int dx)
{
    while(i<maxn)
    {
        tree[i]+=dx;
        i+=lowbit(i);
    }
}
int main()
{
    int n;int i;
    while(scanf("%d",&n)!=EOF)
    {
        memset(tree,0,sizeof(tree));
        int ans[maxn];
        memset(ans,0,sizeof(ans));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            num[i]++;
            ans[0]+=(i⑴)-getsum(num[i]);
            update(num[i],1);
        }
        int sum=ans[0];
        for(i=1;i<=n;i++)
        {
            ans[i]=ans[i⑴]+(n+1)⑵*num[i];
            sum=min(ans[i],sum);
        }
        printf("%d ",sum);
    }
}