题意：有0～n-1数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,每得到一个序列都可得出该序列的逆序数（如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数）。要求求出最小的逆序数。
思路：（一直在做线段树的题，看列表里有这一题。想了很久不会，看解题报告做出来的。）
说一下自己的想法：
1、对于某一序列，其中的某一个数a[i]能构成多少个逆序，只须判断在a[i]+1~n的范围内找之前的数是否出现过的次数；
2、然后求出第一个序列的逆序数。
3、由第一个序列的逆序数可以推出它下一个序列的逆序数。 有规律 下一个序列的逆序数 sum = 上一个的sum - a[i] - 1- a[i];如果得出呢 比如说：
序列 3 6 9 0 8 5 7 4 2 1 把3移到后面，则它的逆序数会减少3个（0 2 1） 但同时会增加 n - a[i] - 1个。 对于1中如何求其出现的次数呢？具体见Update函数 原理是，由开始往后更新，每输一个数就在其对应的位置标志其出现过。如输了 3 6 9 则 node[u].l = node[u].r = 3 6 9 的sum都为1 当输入0时，查找区间1～10内之前输入的有哪些数出现就是它的逆序数 此时 3 6 9 都出现过了。（表达不清 不要见怪 大概就这意思）
//46MS 292K
#include <stdio.h>
#include <string.h>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
const int M = 5005;
struct Node
{
int l,r,sum;
}node[M<<2];
int a[M];
int min (int a,int b)
{
return a > b ? b : a;
}
void Build (int u,int left,int right)
{
node[u].l = left,node[u].r = right;
node[u].sum = 0;
if (node[u].l == node[u].r)
return ;
int mid = (node[u].l + node[u].r)>>1;
Build (L(u),left,mid);
Build (R(u),mid+1,right);
}
void Update(int u,int p)
{
if (node[u].l == node[u].r){
node[u].sum ++;
return ;
}
if (p <= node[L(u)].r) Update(L(u),p);
else Update(R(u),p);
node[u].sum = node[L(u)].sum + node[R(u)].sum; //向上更新 每
}
int Query(int u,int p) //查找区间p~n
{
if (p <= node[u].l)
return node[u].sum;
if (p <= node[L(u)].r)
return Query(L(u),p) + Query(R(u),p);
else return Query(R(u),p);
}
int main ()
{
int n,i;
while (~scanf ("%d",&n))
{
Build(1,0,n);
int sum = 0;
for (i = 0;i < n;i ++)
{
scanf ("%d",&a[i]);
sum += Query(1,a[i]+1);
Update(1,a[i]);
}
int ans = sum;
for (i = 0;i < n;i ++)
{
sum += n - a[i] - a[i] - 1;
ans = min(ans,sum);
}
printf ("%d\n",ans);
}
return 0;
}