1 //Accepted    292 KB    46 ms 2 //利用线段树求逆序数 3 //对于每个数看前面比他大的数有多少个，更新这个数的个数 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 #include <queue> 8 #include <cmath> 9 #include <algorithm>10 using namespace std;11 /**12   * This is a documentation comment block13   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！14   * @authr songt15   */16 const int imax_n = 5005;17 struct node18 {19     int l,r;20     int sum;21 }f[3*imax_n];22 int a[imax_n];23 int n;24 void build(int t,int l,int r)25 {26     f[t].l=l;27     f[t].r=r;28     f[t].sum=0;29     if (l==r)30     {31         return ;32     }33     int mid=(l+r)/2;34     build(2*t,l,mid);35     build(2*t+1,mid+1,r);36 }37 void update(int t,int l)38 {39     if (f[t].l==l && f[t].r==l)40     {41         f[t].sum++;42         return ;43     }44     int mid=(f[t].l+f[t].r)/2;45     if (mid>=l) update(2*t,l);46     else update(2*t+1,l);47     f[t].sum=f[2*t].sum+f[2*t+1].sum;48 }49 int query(int t,int l,int r)50 {51     if (f[t].l==l && f[t].r==r)52     {53         return f[t].sum;54     }55     int mid=(f[t].l+f[t].r)/2;56     if (r<=mid) return query(2*t,l,r);57     else58     {59         if (l>mid) return query(2*t+1,l,r);60         else return query(2*t,l,mid)+query(2*t+1,mid+1,r);61     }62 }63 void slove()64 {65     build(1,1,n);66     int sum=0;67     int ans;68     for (int i=0;i<n;i++)69     {70         update(1,a[i]);71         if (a[i]==n) continue;72         int t=query(1,a[i]+1,n);73         sum+=t;74         //printf("%d ",t);75     }76     //printf("\n");77     //printf("%d\n",sum);78     ans=sum;79     for (int i=0;i<n;i++)80     {81         sum=sum+(n-a[i])-(a[i]-1);82         if (sum<ans) ans=sum;83     }84     printf("%d\n",ans);85 }86 int main()87 {88     while (scanf("%d",&n)!=EOF)89     {90         for (int i=0;i<n;i++)91         {92             scanf("%d",&a[i]);93             a[i]++;94         }95         slove();96     }97     return 0;98 }