題目：HDU1394 Minimum Inversion Number

?

若abcde...的逆序數為k，那么bcde...a的逆序數是多少？我們假設abcde...中小于a的個數為t , 那么大于a的個數就是n-t-1，當把a移動最右位時，原來比a

大的現在都成了a的逆序對，即逆序數增加n-t-1，但是原來比a小的構成逆序對的數，現在都變成了順序，因此逆序對減少t ,所以新序列的逆序數為 k +=

n - t - t -1，即k += n-1-2 * t , 于是我們只要不斷移位（n次），然后更新最小值就可以了

#include <stdio.h> #define maxn 55555#define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1int sum[maxn<<2]; int x[maxn];int min(int a,int b) {return a<b? a:b; }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(lson);Build(rson); }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,lson);elseUpdate(p,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; }int main() {int n,i;while(~scanf("%d",&n)){Build(0,n-1,1);int sum=0;for(i=0;i<n;i++){scanf("%d",&x[i]);sum+=Query(x[i],n-1,0,n-1,1);Update(x[i],0,n-1,1);}int ret=sum;for(i=0;i<n;i++){sum+=n-x[i]-x[i]-1;ret=min(ret,sum);}printf("%d\n",ret);}return 0; }

?

總結

以上是生活随笔為你收集整理的线段树求逆序数(单点更新)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。