学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394

题目大意：给你一个0 -- N-1序列，可以把首位移到最后，求所有变化中逆序数最小的。

解法：首先我们先证明只要求一次逆序数就可以了，不过我觉得是这个题目的特殊性，因为是连续的，所以才能这么做。

比如，现在序列为1 2 3 4 5，我们把1移到最后，变成了2 3 4 5 1

因为第一个是k，放到后面之后会减少k-1个逆序数，然后会增加n-k个逆序数。不过这个题目因为有0而没有n，所以是增加了k，减少了n-k-1

然后由逆序数的定义我们知道，第I个数的前面有k比它大的数，总的逆序数就加k，所以，我们可以在输入的时候利用线段树的特性用区间求和。

如在输入第I个数Num[i]，我们就加上树上【Num[i] ，N】这个区间的数就可以了，当初线段树信息结点初始为0，只有输入一个才加1

详情见代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define rson o*2+1,M+1,R
#define lson o*2,L,M
const int maxn=5100;
const int INF=0x7fffffff;
int a[maxn*3];
void update(int o,int L,int R,int x)
{
    if(L==R)
        a[o]++;
    else{
        int M=(L+R)/2;
        if(x<=M) update(lson,x);
        else update(rson,x);
        a[o]=a[o*2]+a[o*2+1];
    }
}
int query(int o,int L,int R,int x,int y)
{
    if(x<=L && y>=R) return a[o];
    else{
        int M=(L+R)/2,ans=0;
        if(x<=M) ans+=query(lson,x,y);
        if(y>M) ans+=query(rson,x,y);
        return ans;
    }
}
int main()
{
    int n;
    while (scanf("%d",&n)==1)
    {
        memset(a,0,sizeof(a));//建树。。。
        int sum=0,num[maxn];
        for(int i=1;i<=n;i++)
        {
            scanf("%d",num+i);
            sum+=query(1,0,n-1,num[i],n);
            update(1,0,n-1,num[i]);
        }
        int ans=sum;
        for(int i=1;i<n;i++)
        {
            sum=sum-(num[i])+(n-num[i]-1);
            ans=min(ans,sum);
        }
        cout<<ans<<endl;
    }
    return 0;
}