HDOJ 1394 Minimum Inversion Number 线段树 : 单点更新 成段求和

//HDOJ 1394 Minimum Inversion Number  线段树 : 单点增加　成段求和
/*
题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意：已知一个数列，数列个数ｎ<=5000，数列中的数的范围在[0,n-1]，并且数不重复。每次可以将数列的第一个数移动到

最后面，这样可以构造出ｎ个数列。求这这ｎ个数列中的最小逆序数。

思路：逆序数可以理解成该数字前面有多少比它大的数，这样就可以转化为线段树求解。线段树的结点中记录改结点是否被占

用，即这个数字在前面是否出现过。然后从改数列的第一个数开始，先查询比这个数大的区间中被占用的个数，累加到结果上

，然后更新这个数到线段树中，标记这个数被占用。这样在ｎ次查询和ｎ次更 新后，线段树建立的同时就已经计算出了这个

数列的逆序数。但是这里一共有ｎ个数列，如果重复ｎ次这样的操作，复杂度将上升到Ｏ（ｎ^2longn），会超时。其实这里

只要计算第一次的逆序数，其他数列的逆序数可以用这个已经计算好的逆序数推出。具体的做法是：当第一个数移动到最后面

时，假如这个数是ａ，那么这个数后面会有n-a-1个数比它大，a个比它小，移动后，这个数的逆序数会增加n-a-1，其它数的

逆序数会减小a，所以总的来说逆序数会增加n- a-1-a。这样只要计算再ｎ－１次计算就可以得到每个序列的逆序数了，取期

中最小的就是结果了。这样时间复杂度为Ｏ（nlogn）。
*/

#include<stdio.h>
#include<string.h>

#define N 5005

int t[N<<2];
int n,num[N],v[N];

void PushUp(int rt){
    t[rt] = t[rt<<1] + t[rt<<1|1];
}

void update(int rt,int l,int r,int x){
    if(l == r){
        t[rt]++;
        return ;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) update(rt<<1,l,mid,x);
    else update(rt<<1|1,mid+1,r,x);
    PushUp(rt);
}

int query(int rt,int l,int r,int L,int R){
    if(L <= l && R>=r)
        return t[rt];
    int mid = (l + r) >>1;
    int res = 0;
    if(L <= mid) res += query(rt<<1,l,mid,L,R);
    if(R > mid ) res += query(rt<<1|1,mid+1,r,L,R);
    return res;
}

int main(){
    int i,sum;
    while(scanf("%d",&n)!=EOF){
        memset(t,0,sizeof(t));
        sum = 0;
        for(i = 1; i <= n; ++i){
            scanf("%d",&v[i]);
            sum += query(1,0,n-1,v[i],n);
            update(1,0,n-1,v[i]);
        }
        int res = sum;
        for(i = 1; i <= n; ++i){
            sum += n-1-v[i]-v[i];
            if(sum < res)
                res = sum;
        }
        printf("%d\n",res);
    }
    return 0;
}