HDU 1394

题意：

给一个由0~n-1组成的序列，求出该序列的所有循环同构序列中的最小逆序对数目，逆序对的两个元素可以不相邻。

思路：

这题据说可以直接暴力 O(n2) 可以水过。。
说一下线段树做法 O(nlogn) :
以这个序列来说明：
1,9,2,3,0,8,5,7,4,6

我们先假设有一个长度为n元素全为0的数组：
0,0,0,0,0,0,0,0,0,0

我们先计算所给序列的第一项1（实际上是第0项）的数字所对应位置之后所有元素的和（括号里面的数），和就是当前与这个数逆序的数的个数，这样做避免了重复统计逆序对，我们把它累计起来：
0,(0,0,0,0,0,0,0,0,0)，sum+=0;

我们将所给序列的第一项的数字所对应位置置1：
0,1,0,0,0,0,0,0,0,0

第二项9：
0,1,0,0,0,0,0,0,0,(0)，sum+=0;

0,1,0,0,0,0,0,0,0,1

第三项2：
0,1,(0,0,0,0,0,0,0,1)，sum+=1;
（2与9逆序）
0,1,1,0,0,0,0,0,0,1

第四项3：
0,1,1,(0,0,0,0,0,0,1)，sum+=1;
（3与9逆序）
0,1,1,1,0,0,0,0,0,1

第五项0：
(0,1,1,1,0,0,0,0,0,1)，sum+=4;
（0与1,2,3,9逆序）
1,1,1,1,0,0,0,0,0,1

以此类推到最后，sum便是该序列逆序对个数。

现在考虑循环同构序列的最小值：

刚才的序列：
1,9,2,3,0,8,5,7,4,6

我们把x0 = 1移到最后：
9,2,3,0,8,5,7,4,6,1

发现逆序对增加了8对（8 = 10 - x0 - 1），减少了1对（1 = x0），可以推出结论，向后移动一个数字，逆序对增加n - xi - 1，减少xi。扫一遍维护最小值即可。

代码：

/*
* @author FreeWifi_novicer
* language : C++/C
*/
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
         
        
       
      
     
    
   

?