http://acm.hdu.edu.cn/showproblem.php?pid=1394
题意：给定一个长度为n的序列，每次操作可以把序列前面的m个数移到序列后面去
求在每次操作下的序列最小的逆序对数。
题解：
我们可以考虑用线段树先求出初始序列的逆序对数。对于移动m个数等价于
先移动m-1个数再移动1个数，那我们只要移动当前的ai就可以得出所有的结果。
实际上，把一个数移到后面去对整体逆序对的影响是：本来在ai后面比ai小的数与
ai构成的逆序对不复存在，有ai个（因为数组从0开始所以不是ai-1）然后在ai后面
比ai大的数将会与它构成新的逆序对，有n-1-ai个，那么移动当前ai的结果就是n-1-ai-ai
分析到这里，题目就做完了，下面是代码：
1 #define bug(x,y) cout<<"i="<<x<<": "<<y<<endl 2 #define IO std::ios::sync_with_stdio(0); 3 #include <bits/stdc++.h> 4 #define itor ::iterator 5 using namespace std; 6 typedef long long ll; 7 typedef pair<ll,ll>P; 8 #define pb push_back 9 #define se second 10 #define fi first 11 #define rs o*2+1 12 #define ls o*2 13 const int N=5e3+5; 14 int n; 15 int sumv[N*4],a[N]; 16 void build(int o,int l,int r){ 17 sumv[o]=0; 18 if(l==r){ 19 return; 20 } 21 int m=(l+r)/2; 22 build(ls,l,m); 23 build(rs,m+1,r); 24 } 25 void up(int o,int l,int r,int p){ 26 if(l==r){ 27 sumv[o]=1; 28 return; 29 } 30 int m=(l+r)/2; 31 if(p<=m)up(ls,l,m,p); 32 else up(rs,m+1,r,p); 33 sumv[o]=sumv[ls]+sumv[rs]; 34 } 35 int query(int o,int l,int r,int ql,int qr){ 36 if(l>=ql&&r<=qr){ 37 return sumv[o]; 38 } 39 int m=(l+r)/2; 40 int res=0; 41 if(ql<=m)res+=query(ls,l,m,ql,qr); 42 if(qr>m)res+=query(rs,m+1,r,ql,qr); 43 return res; 44 } 45 int main(){ 46 while(~scanf("%d",&n)){ 47 build(1,0,n-1); 48 ll ans=0; 49 for(int i=1;i<=n;i++){ 50 scanf("%d",&a[i]); 51 int res=query(1,0,n-1,a[i]+1,n-1); 52 //bug(i,res); 53 ans+=res; 54 up(1,0,n-1,a[i]); 55 } 56 ll h=ans; 57 for(int i=1;i<n;i++){ 58 h+=(n-1-a[i]-a[i]); 59 ans=min(ans,h); 60 } 61 printf("%lld ",ans); 62 } 63 } 64 /* 65 5 66 2 1 0 4 3 67 */