POJ - 2299 Ultra-QuickSort 求逆序对数(树状数组离散化/归并排序)-白红宇

POJ - 2299 Ultra-QuickSort 求逆序对数(树状数组离散化/归并排序)

阅读量：2135 次

发布时间：2019-04-30

本文共 1576 字，大约阅读时间需要 5 分钟。

题目大意：给出一个序列，求将它们冒泡排序的交换次数。

题解：

①树状数组求逆序对数的一个典例题，但要注意需要离散化，因为n的范围是5e5，而a[i]的范围是1e10，数组开不了1e10那么大，所以离散化一下，只需要开到5e5就可以了

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define ll long long#define INF 1000000007int n;int order[500010];int c[500010];struct node{    int v,id;}a[500010];int lowbit(int x){    return x & -x;}void add(int i,int val)// Add操作，将第i个元素增加val，那么他的父节点也要增加+{    while(i<=n)    {        c[i]+=val;        i+=lowbit(i);    }}int sum(int i){    int s=0;    while(i>0)    {        s+=c[i];        i-=lowbit(i);    }    return s;}bool cmp(node a,node b){    return a.v

②归并排序求逆序对数，模板题

#include
   
    #include
    
     #include
     
      #define ll long longusing namespace std;ll a[500010],t[500010];ll ans(0);void Merge(int l,int m,int r) //左(l,m)右(m,r)两个表合并成一个表{                             //最后排序结果还是会存在a数组里    int i=l,j=m+1,cnt=0;    while(i<=m && j<=r)       //i扫左一半,j扫右一半    {        if(a[i]<=a[j])            t[cnt++]=a[i++];        else        {            ans+=m-i+1;  //核心代码，求解逆序数个数。            t[cnt++]=a[j++];        }    }    while(i<=m) //若左表不空        t[cnt++]=a[i++];    while(j<=r) //若右表不空        t[cnt++]=a[j++];    for(int k=0;k
      
       >1;        Merge_sort(l,m);        Merge_sort(m+1,r);        Merge(l,m,r);    }}int main(){    //freopen("input.txt","r",stdin);    ios::sync_with_stdio(false);    cin.tie(0);    int n;    while(cin>>n && n)    {        for(int i=0;i
       
        >a[i];        ans=0;        Merge_sort(0,n-1);        cout<
        
         <<"\n"; } return 0;}