题目：点击打开题目链接

题意：输入一个初始序列，然后每次操作都把序列的第一个数放到最后一个位置，构成一个新的序列，问其中某一个序列的最小逆序数是多少。

思路：首先，普及一下逆序与逆序数的概念，简单地说就是如果前面的数比后面的数大，就称为一个逆序。一个排列中逆序的总数称为这个排列的逆序数。

然后这道题有一个好处就是这n个数是由0~n-1组成的，那么，这意味着什么呢？仔细观察后，我们不难发现

假设0~n-1中的一个数x放到了最后一个位置，那么这个序列的逆序数就是n-1-x，这是为什么呢，下面我们接着看

因为在这个序列中，比x小的数有x个（始终记住这n个数是由0~n-1组成的），比x大的数有n-1-x个，那么，将x放到最后一个位置，也就是说，这个序列中的前n-1个数（去掉最后一个数）中有x个比它小的数，有n-1-x个比它大的数，所以这个序列的逆序数就是n-1-x。

我们假设初始序列的逆序数是ans，那么把序列中的x放到最后一个位置之后，逆序数就变成了ans - x +（n-1-x），减x是因为原本x是第一个数，后面有x个比它小的数，现在把它放到了最后一个位置，那么序列中前面有x个对于x来说是有序的，只有那n-1-x个比它大的数才是逆序，所以逆序数要-x。

所以问题就转化成了求初始序列的逆序数，用线段树的方法单点更新，区间求和

主要思想就是把每个数放到自己的叶子结点，然后看它前面有多少个比它大的数，最后累加就是序列的逆序数。

My  DaiMa：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define lson l,mid,num<<1
#define rson mid+1,r,num<<1|1
const int maxn = 5005;
int sum[maxn<<2];
void push_up(int num)
{
    sum[num] = sum[num<<1] + sum[num<<1|1];
}
/*建树*/
void TreeBuild(int l,int r,int num)
{
    sum[num] = 0;//初始都是0
    if(l == r) return;
    int mid = (l+r) >> 1;
    TreeBuild(lson);
    TreeBuild(rson);
    push_up(num);
}
/*每插入一个数，更新*/
void update(int x,int l,int r,int num)
{
    if(l == r)
    {
        sum[num] ++;
        return;
    }
    int mid = (l+r) >> 1;
    if(x > mid) update(x,rson);
    else update(x,lson);
    push_up(num);
}
/*查询，判断前面有多少个比它大的数*/
int query(int x,int y,int l,int r,int num)
{
    if(x <= l && y >= r) return sum[num];
    int ans = 0;
    int mid = (l+r) >> 1;
    if(x <= mid) ans += query(x,y,lson);
    if(y > mid) ans +=query(x,y,rson);
    return ans;
}
int main()
{
    int n,a[5005];
    while(cin >> n)
    {
        TreeBuild(0,n-1,1);
        int ans = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d",&a[i]);
            ans += query(a[i],n-1,0,n-1,1);//先查询
            update(a[i],0,n-1,1);//后更新
        }
        int minn = ans;
        for(int i = 0; i < n; i++)
        {
            ans = ans - a[i] + (n - 1 - a[i]);
            minn = min(minn,ans);
        }
        cout << minn << endl;
    }
}