HDU 1394 Minimum Inversion Number（线段树，逆序数）

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1394

题目大意：

给一个n个数的序列a1, a2, ..., an ，这些数的范围是0～n-1， 可以把前面m个数移动到后面去，形成新序列：

a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
求这些序列中，逆序数最少的是多少？

分析与总结：

（1） 初看这题时，觉得眼熟，于是翻看了交题记录，原来去年做过 = =，不过那时是直接暴力求出逆序数水过的...

然后就想这样用线段树来优化。所谓的求逆序数，其实就是序列中的每一个数，它前面的比他大的数的数量之和。

用线段树记录下各个数，区间的值【a,b】表示数字a～b的已经出现了多少次，所以对于ai，只需要查询【ai, n】有多少个(ai之前的比ai大的有多少个)，就是代表ai有多少个逆序数了。

（2） 求出a1, a2, ..., an-1, an的逆序数之后，就可以递推求出其他序列的逆序数。 假设要把a1移动到an之后，那么我们把这个过程拆分成两步：

1. 把a1去除掉。通过观察可以发现，（a1-1）是0～n-1中比a1小的数字的个数，由于a1在序列的第一个所以a1之后共有(a1-1)个比a1小，所以形成了（a1-1）对逆序数，当去除掉a1时，原序列的逆序数总数也就减少了（a1-1）个逆序数。

2. 把a1加到an之后。0～n-1中，比a1大的数共有（n-a1）个数，由于a1现在在最后一个，也就是它前面共有（n-a1）个数比它大，即增加了（n-a1）对逆序数。

综合1，2两步， 设原序列逆序数为sum, 当把原序列第一个移动到最后位置时，逆序数变为：sum = sum-(ai-1)+(n-ai);

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define lson(x) (x<<1)
#define rson(x) (lson(x)|1)
using namespace std;

const int MAX_NODE = 5005 << 2;
int arr[MAX_NODE];

struct node{
    int left, right;
    int num;
    int mid(){return (left+right)>>1;}
    bool buttom(){return left==right;}
};

class SegTree{
public:
    void build(int cur,int left,int right){
        t[cur].left  = left;
        t[cur].right = right;
        if(left == right){
            t[cur].num = 0;
            return;
        }
        int m = t[cur].mid();
        build(lson(cur),left,m);
        build(rson(cur),m+1,right);
        push_up(cur);
    }
    void update(int cur,int data){
        ++t[cur].num;
        if(t[cur].buttom()){
            return;
        }
        int m = t[cur].mid();
        if(data <= m)
            update(lson(cur),data);
        else
            update(rson(cur),data);
    }
    int query(int cur,int left,int right){
        if(t[cur].left==left && t[cur].right==right){
            return t[cur].num;
        }
        int m=t[cur].mid();
        if(right <= m)
            return query(lson(cur),left,right);
        else if(left > m)
            return query(rson(cur),left,right);
        else 
            return  query(lson(cur),left,m)+query(rson(cur),m+1,right);
    }

private:
    void push_up(int cur){
        t[cur].num = t[lson(cur)].num+t[rson(cur)].num;
    }
    node t[MAX_NODE];
};

SegTree st;

int main(){
    int n,x;
    while(~scanf("%d",&n)){
        st.build(1,1,n);
        int sum=0;
        for(int i=0; i<n; ++i){
            scanf("%d",&arr[i]);
            ++arr[i];
            int tmp = st.query(1,arr[i],n);
            sum += tmp;
            st.update(1,arr[i]);
        }
        int _min = sum;
        for(int i=0; i<n-1; ++i){
            sum = sum-(arr[i]-1)+(n-arr[i]);
            if(sum < _min) _min=sum;
        }
        printf("%d\n",_min);
    }
    return 0;
}

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)