Minimum Inversion Number

传送门

#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
const int N=5005;
int sum[N<<2];
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void updata(int p,int ad,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]+=ad;
        return;
    }
    int m=l+r>>1;
    if(p<=m)
        updata(p,ad,lson);
    else
        updata(p,ad,rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        return sum[rt];
    }
    int m=l+r>>1;
    int ret=0;
    if(L<=m)
        ret+=query(L,R,lson);
    if(R>m)
        ret+=query(L,R,rson);
    return ret;
}
#if 1
void build(int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]=0;
        return;
    }
    int m=l+r>>1;
    build(lson);
    build(rson);
    pushup(rt);//这种方式建树必须调用函数
}
#endif
#if 0
void build(int l,int r,int rt)
{
    sum[rt]=0;
    if(l==r)
        return;
    int m=l+r>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
#endif
int main()
{

    int n,arr[N];
    while(scanf("%d",&n)!=EOF)
    {
        build(1,n,1);
        ll ans=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&arr[i]);
            updata(arr[i]+1,1,1,n,1);
            ans=ans+i-query(1,arr[i]+1,1,n,1);
            //ans=ans+query(arr[i]+1,n,1,n,1);
            //updata(arr[i]+1,1,1,n,1);
        }
        ll minn=ans;
        for(int i=1; i<=n; i++)
        {
            ans=ans+n-2*arr[i]-1;
            minn=min(ans,minn);
        }
        printf("%lldn",minn);
    }
    return 0;
}

**树状数组不能使用下标0，线段树可以使用下标0

最后

以上就是现实大树为你收集整理的HDU-1394(线段树)Minimum Inversion Number的全部内容，希望文章能够帮你解决HDU-1394(线段树)Minimum Inversion Number所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。