nyist oj 117 求逆序数 (归并排序&&树状数组） - c++编程基础

求逆序数

时间限制：2000 ms | 内存限制：65535 KB 难度：5

描述

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

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

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

输入

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

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

输出

输出该数列的逆序数

样例输入

样例输出

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