http://acm.hdu.edu.cn/showproblem.php?pid=1394

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxn 50000 5 using namespace std; 6  7 struct node 8 { 9     int l,r;10     int ans;11 }tree[maxn*4];12 13 void build(int i,int l,int r)14 {15     tree[i].l=l;tree[i].r=r;16     tree[i].ans=0;17     if(l==r) return ;18     int mid=(l+r)>>1;19     build(i<<1,l,mid);20     build(i<<1|1,mid+1,r);21 }22 23 int search1(int i,int l,int r)24 {25     if(tree[i].l==l&&tree[i].r==r)26     {27         return tree[i].ans;28     }29     int mid=(tree[i].l+tree[i].r)>>1;30     if(r<=mid)31     {32         return search1(i<<1,l,r);33     }34     else if(l>mid)35     {36         return search1(i<<1|1,l,r);37     }38     else39     {40         return search1(i<<1,l,mid)+search1(i<<1|1,mid+1,r);41     }42 }43 44 void update(int i,int c)45 {46     tree[i].ans++;47     if(tree[i].l==tree[i].r) return ;48     int mid=(tree[i].l+tree[i].r)>>1;49     if(c<=mid)50     {51         update(i<<1,c);52     }53     else54     {55         update(i<<1|1,c);56     }57 }58 59 int main()60 {61     int a[maxn],n;62     while(scanf("%d",&n)!=EOF)63     {64         build(1,0,n-1);65         int sum=0;66         for(int i=1; i<=n; i++)67         {68             scanf("%d",&a[i]);69             sum+=search1(1,a[i],n-1);70             update(1,a[i]);71         }72         int cc=sum;73         for(int i=1; i<=n; i++)74         {75             sum+=(-a[i]+n-a[i]-1);76             cc=min(cc,sum);77         }78         printf("%d\n",cc);79     }80     return 0;81 }