【线段树】hdu 1394 Minimum Inversion Number

本文主要是介绍【线段树】hdu 1394 Minimum Inversion Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意:求Inversion后的最小逆序数
思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解
线段树功能:update:单点增减 query:区间求和

#include<iostream>
#include<algorithm>
using namespace std;
int sum[10001],x[5001];
void pushup(int rt)
{sum[rt]=sum[rt<<1]+sum[(rt<<1)+1];
}
void build(int l,int r,int rt)
{sum[rt]=0;if (l==r) return;int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)+1);
}
void update(int p,int l,int r,int rt)
{if(l==r){sum[rt]++;return;}int m=(l+r)>>1;if(p<=m)update(p,l,m,rt<<1);else update(p,m+1,r,(rt<<1)+1);pushup(rt);
}
int ge(int L,int R,int l,int r,int rt)
{if(L<=l&&r<=R)return sum[rt];int m=(l+r)>>1,ret=0;if(L<=m)ret+=ge(L,R,l,m,rt<<1);if(R>m)ret+=ge(L,R,m+1,r,(rt<<1)+1);return ret;
}
int main()
{ios::sync_with_stdio(false);int n;while (cin>>n){build(0,n-1,1);int sum=0;for (int i=0;i<n;i++){cin>>x[i];sum+=ge(x[i],n-1,0,n-1,1);update(x[i],0,n-1,1);}int ret=sum;for (int i=0;i<n;i++){sum+=n-1-x[i]-x[i];ret=min(sum,ret);}cout<<ret<<endl;}
}

这篇关于【线段树】hdu 1394 Minimum Inversion Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---