HDU 1394 Minimum Inversion Number


		看了Not Only Success 的分类和题解。。
首先求出原序列的逆序数,as，
然后假设当前队首元素为a，
那么a之后有a-1个比a小的元素，有n-a个比a大的元素，
当把a放在队尾时，比a小的元素的逆序数-1，即as-=a-1
而对于a来说，前面比a大的元素又各增加了1个逆序对，即as+=n-a，
于是枚举一次就可以找到最小的as了。
 
这里是线段树求逆序对算法：
build的过程相当于insert的过程，就是把值为x的元素插到线段树中，
然后求当前x+1,n的元素的个数y，就是新生成逆序对的个数，即as+=y。
[cpp] 
#include<stdio.h>  
#define lson l,mid,rt*2  
#define rson mid+1,r,rt*2+1  
#define X 5010  
int a[X*4],b[X],ll,rr;  
void pushup(int rt){  
    a[rt]=a[rt*2]+a[rt*2+1];  
}  
void build(int x,int l,int r,int rt){  
    if(l==r){a[rt]++;return ;}  
    int mid=l+r>>1;  
    if(x<=mid)build(x,lson);  
    else      build(x,rson);  
    pushup(rt);  
}  
int que(int l,int r,int rt){  
    if(ll<=l&&rr>=r)return a[rt];  
    int as=0,mid=l+r>>1;  
    if(ll<=mid)as+=que(lson);  
    if(rr>mid) as+=que(rson);  
    return as;  
}  
int main(){  
    int i,n,x,as,tmp;  
    while(~scanf("%d",&n)){  
        for(i=1;i<=n*4;i++)a[i]=0;  
        tmp=0;as=n*n;  
        for(i=1;i<=n;i++)  
            scanf("%d",&b[i]),b[i]++;  
        for(i=1;i<=n;i++){  
            ll=b[i],rr=n;  
            tmp+=que(1,n,1);  
            build(b[i],1,n,1);  
        }  
        for(i=1;i<n;i++){  
            tmp+=n+1-2*b[i];  
            as=tmp<as?tmp:as;  
        }  
        printf("%d\n",as);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,