【题目描述】

思路{

　　首先贪心地想，应该是小怼小，大怼大。即A(i)<=A(i+1),B(i)<=B(i+1),这是排序不等式

　　证明它，我们需要使用和式恒等变换（感谢朱峰昊（朱哥）的大力支持）{

　　　　设A(i)<=A(i+1),B(i)<=B(i+1),证明：

　　　　　　∑A(i)*B(i)（顺序和）

　　　　　　>=∑A(i)*B( j(i) )（乱序和）

　　　　　　>=∑A(i)*B(n-i+1)（逆序和）

　　　　　　其中j(i)为一个任意的对应关系。

　　　　　　设S[i]=∑B(k)(k<=i),S'[i]=∑B(  j(k) );易知，S[i]<=S‘[i]；又因为A(i)<=A(i+1)

　　　　　　所以S[i]*(A[i+1]-A[i])>=S’[i]*(A[i+1]-A[i])

　　　　　　∑A(i)*B(i)=∑S[i]*(A[i+1]-A[i])(i<=n-1)+A[n]*B[n]

                   >=∑S‘[i]*(A[i+1]-A[i])(i<=n-1)+A[n]*B[n]

                   =∑A(i)*B( j(i) );

　　　　　　                       同理证得右边也成立，问题得证。

　　        }

　　问题解的min为∑（A[i]-B[i]）^2=∑A[i]^2+∑B[i]^2-2∑A(i)*B(i).

　　前两项是恒定的，故后一项取最大即可，即为顺序和。

        可以统计出每个位置当前点所对应的下标pos[i]。首状态是位置依次递增的。

        而末状态为pos[i],pos[i+1]......pos[n];

        要统计多少步，不妨反过来考虑。

        由于交换两个数只改变这两个数所成的逆序对。

        反过来考虑，就是把一个存在逆序对的数组变成一个非严格上升的子序列，

        且每次交换操作只改变一对。

        那么，只需要用树状数组统计pos下标的逆序对就可以了。

}

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include