1 #include <stdio.h> 2 #define lson l,mid,id<<1 3 #define rson mid+1,r,id<<1|1 4 const int MM= 5001; 5 int sum[MM<<2]; 6  7 void build_tree(int l,int r,int id) 8 { 9     sum[id]=0;10     if(l==r)11     {12         return;13     }14     else15     {16         int mid=(l+r)>>1;17         build_tree(lson);18         build_tree(rson);19     }20     21 }22 int Query(int L,int R,int l,int r,int id)23 {24     if(L<=l&&r<=R)25     {26         return sum[id];27     }28     else29     {30         int mid=(l+r)>>1;int ret=0;31         if(L<=mid)ret+=Query(L,R,lson);32         if(R>mid)ret+=Query(L,R,rson);33         return ret;34     }35 }36 void update(int pos,int l,int r,int id)37 {38     if(l==r)39     {40         sum[id]++;return;41     }42     else{43         int mid=(l+r)>>1;44         if(pos<=mid)update(pos,lson);45         if(pos>mid)update(pos,rson);46         sum[id]=sum[id<<1]+sum[id<<1|1];47     }48 }49 int main()50 {51     int n,i,seg[MM];52     while(~scanf("%d",&n))53     {54         build_tree(0,n-1,1);55         int ans=0;56         for(i=0;i<n;i++)57         {58             scanf("%d",&seg[i]);59             ans+=Query(seg[i],n-1,0,n-1,1);60         /*61             +比seg[i]大的数，按输入顺序，因为每个数都不会超过n,所以简单了许多62         */63             update(seg[i],0,n-1,1);64         }65         int min=ans;66         for(i=0;i<n;i++)67         {68             ans+=n-seg[i]*2-1;69             /*70                 比seg[i]小的-seg[i],seg[i]移到最后，+(n-seg[i]-1)71             */72             if(ans<min)73             {74                 min=ans;75             }76         }77         printf("%d\n",min );78     }79 }