题意
给定一个排列.
将该排列的第一个数移动到最后面，重复n-1次，形成总共n个排列。
问哪个排列中所含逆序对最少，输出最少逆序对数。
题解
求逆序对有很多种方法，O（n^2)的暴力，O（nlogn)的树状数组、归并排序等。
这里，采用的是权值线段树。
所谓权值线段树，就是用数值去建立线段树，每个结点所代表的区间[l，r]维护的是值在[l，r]中出现的次数。
这样，每插入一个值x，查询当前线段树[x+1，n]的值的个数，累加到逆序对总数中去。查询完后，线段树中值为x的总数加1.
AC代码
//46ms
#include <bits/stdc++.h>
#define lson p<<1
#define rson p<<1|1
using namespace std;const int maxn=5e3+7;
struct node
{int l,r,cnt;
}T[maxn<<2];void up(int p)
{T[p].cnt=T[lson].cnt+T[rson].cnt;
}
void build(int p,int x,int y)
{T[p].l=x,T[p].r=y;if(x==y){T[p].cnt=0;return ;}int mid=(x+y)>>1;build(lson,x,mid);build(rson,mid+1,y);up(p);
}
void update(int p,int x)//将第x个值的数加1
{if(T[p].l==T[p].r){T[p].cnt++;return ;}int mid=(T[p].l+T[p].r)>>1;if(x<=mid) update(lson,x);else update(rson,x);up(p);
}
int query(int p,int x,int y)//查询权值在区间[x,y]的数的数量
{if(x>y) return 0;if(T[p].l==x && T[p].r==y){return T[p].cnt;}int mid=(T[p].l+T[p].r)>>1;if(y<=mid) return query(lson,x,y);else if(x>mid) return query(rson,x,y);else return query(lson,x,mid)+query(rson,mid+1,y);}
int a[maxn];
int main()
{int n;while(~scanf("%d",&n)){build(1,1,n);int ans=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);a[i]=x;x++;ans+=query(1,x+1,n);update(1,x);}int res=ans;for(int i=1;i<=n;i++){ans=ans-a[i]+n-a[i]-1;res=min(res,ans);}printf("%d\n",res);}return 0;
}