题目链接：

思路：求最小的逆序数。。。可以暴力，也可以用线段树来做。。。下面是用线段树实现的代码：

1 #include
      
        2 const int MAXN=5007; 3 using namespace std; 4 int sum[MAXN<<2]; 5 int x[MAXN]; 6  7 //更新父结点信息 8 void Push_Up(int rt){ 9     sum[rt]=sum[rt<<1]+sum[rt<<1|1];10 }11 12 void Build(int l,int r,int rt){13     sum[rt]=0;14     if(l==r)return ;15     int m=(l+r)/2;16     Build(l,m,rt<<1);17     Build(m+1,r,rt<<1|1);18 }19 20 //单点更新21 void Updata(int p,int l,int r,int rt){22     if(l==r){23         sum[rt]++;24         return ;25     }26     int m=(l+r)>>1;27     if(p<=m)Updata(p,l,m,rt<<1);28     else Updata(p,m+1,r,rt<<1|1);29     Push_Up(rt);30 }31 32 int query(int L,int R,int l,int r,int rt){33     if(L<=l&&r<=R){34         return sum[rt];35     }36     int m=(r+l)>>1;37     int ret=0;38     if(L<=m)ret+=query(L,R,l,m,rt<<1);39     if(R>m)ret+=query(L,R,m+1,r,rt<<1|1);40     return ret;41 }42 43 44 int main(){45     int n;46     while(~scanf("%d",&n)){47         Build(0,n-1,1);48         int s=0;49         for(int i=0;i