题目地址：HDU 1394

这题可以用线段树来求逆序数。

这题的维护信息为每个数是否已经出现。每次输入后，都从该点的值到n-1进行查询，每次发现出现了一个数，由于是从该数的后面开始找的，这个数肯定是比该数大的。那就是一对逆序数，然后逆序数+1.最后求完所有的逆序数之后，剩下的就可以递推出来了。因为假如目前的第一个数是x，那当把他放到最后面的时候，少的逆序数是本来后面比他小的数的个数。多的逆序数就是放到后面后前面比他大的数的个数。因为所有数都是从0到n-1.所以比他小的数就是x，比他大的数就是n-1-x。这样的话每次的逆序数都可以用O(1)的时间计算出来。然后找最小的时候就可以了。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 const int MAXN=6e3; int sum[MAXN<<2], a[MAXN]; void PushUp(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l, int r, int rt) { sum[rt]=0; if(l==r) { return ; } int mid=l+r>>1; build(lson); build(rson); } void update(int p, int l, int r, int rt) { if(l==r) { sum[rt]++; return ; } int mid=l+r>>1; if(p<=mid) update(p,lson); else update(p,rson); PushUp(rt); } int query(int ll, int rr, int l, int r, int rt) { if(ll<=l&&rr>=r) { return sum[rt]; } int mid=l+r>>1; int ans=0; if(ll<=mid) ans+=query(ll,rr,lson); if(rr>mid) ans+=query(ll,rr,rson); return ans; } int main() { int n, i, ans, y; while(scanf("%d",&n)!=EOF) { build(0,n-1,1); ans=0; for(i=0; i