求逆序数

描述

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

输入

第一行输入一个整数T表示测试数据的组数（1<=T<=5)
每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）
随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。

数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。

输出

输出该数列的逆序数

样例输入

2
2
1 1
3
1 3 2

样例输出

0
1

来源

[张云聪]原创

上传者

张云聪
求逆序数：用归并排序来做，效率还是很高的； 归并排序利用分治的思想，先把一个数组分成一个个序列，然后对一个个序列排序，把排好序的序列，在合并到原来的数组中。

#include 
      
       
#include 
       
         #include 
        
          using namespace std; const int maxn=1000001; int a[maxn],b[maxn]; long long sum; void Merge(int begin,int mid,int end)//归并 { int i=begin,j=mid+1,pos=begin; while(i<=mid && j<=end)//对一个个序列排序的过程 { if(a[i]<=a[j]) { b[pos++]=a[i++]; } else { b[pos++]=a[j++]; sum+=mid-i+1;//求逆序数 } } while(i<=mid) b[pos++]=a[i++]; while(j<=end) b[pos++]=a[j++]; for(int i=begin,j=begin;i<=end;i++,j++) a[i]=b[j]; } void Sort(int begin,int end)//排序 { if(begin
         
          
 
          用树状数组求逆序数： 
          
 
           
           
#include 
            
             
#include 
             
               #include 
              
                using namespace std; const int maxn=1000005; struct node { int val,id; }s[maxn]; int a[maxn],n; int lowbit(int i)//位运算 { return i&(-i); } void update(int i)//更新 { while(i<=n) { a[i]++; i+=lowbit(i); } } int sum(int i)//求和 { int sum=0; while(i>0) { sum+=a[i]; i-=lowbit(i); } return sum; } bool cmp(node x,node y)//比较函数 { if(x.val!=y.val) return x.val
               
                
 
                
 
                
 
                 
 
                
               
              
             
            
          
         
        
       
      

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力??

上一篇： poj 2192 zipper

下一篇： POJ 1182 食物链(种类并查集)

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");