求逆序对的方法【逆序对】【树状数组】【归并排序】

作者: wjyyy 分类: 学习笔记,归并,快速排序,数据结构,树状数组 发布时间: 2018-06-05 13:35

点击量:35

   题面可见洛谷P1908逆序对

 

   逆序对,最朴素的做法就是\(O(N^2)\)的了,枚举每个数对,逆序则sum++。

 

   不过主流做法是归并排序,也可以用树状数组(线段树)来做。

 

一、归并排序

归并排序的做法就不再赘述,主要是什么时候求逆序对的问题

   在这个图中,前4个和后4个都是有序的。所以逆序对只会在前面的数与后面比它小的数中出现。我们把这个数组看作两个栈,s1和s2。

 

   第一个出栈的是s2的‘1’,此时在s1的一定全部比它大。所以将逆序对的数目加上s1.size()。(实际应用中加的是数组的长度)

 

   所以在后面元素出栈时,给逆序对个数带来的贡献分别是:1:4   3:3   6:1   8:0。

 

   之后这个序列就是有序的了,它的内部不再有逆序对。

Code:

#include<iostream>
using namespace std;
int a[111111];
int b[111111];
unsigned long long int sum=0;
int num;
void merging(int l1,int r1,int l2,int r2)
{
    int i=l1;
    int j=l2;
    int k=l1;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<=a[j])//求逆序对
            b[k++]=a[i++];
        else
        {
            b[k++]=a[j++];
            sum++;
            sum+=r1;
            sum-=i;
        }
    }
    while(i<=r1)
        b[k++]=a[i++];
    while(j<=r2)
        b[k++]=a[j++];
    for(int i=l1;i<=r2;i++)
        a[i]=b[i];
}
void merged(int l,int r)
{
    if(l==r)
        return;
    int mid;
    mid=(l+r)/2;
    merged(l,mid);
    merged(mid+1,r);
    merging(l,mid,mid+1,r);
}
int main(void)
{
    cin>>num;
    for(int i=1;i<=num;i++)
        cin>>a[i];
    merged(1,num);
    cout<<sum;
}

 

 

二、树状数组

   树状数组的做法看上去要直观一些,比归并排序稍微好理解一点,但是需要\(Nlog N\)的预处理。这样一来常数就基本是2了。

 

   首先,我们要对被处理数组离散化,重复的数字映射为同一个象。然后建立长度为n的树状数组(需满足操作单点增加和区间求和),初始化为0。

 

   然后,从前到后扫描被处理数组。设当前为第k个数,那么a[k]的象为\(f(a[k])\),当扫描到k时,查询在这个数前面(也就是已经被处理的1到k-1)出现过多少个比a[k]大的数,等价于求有多少个象比\(f(a[k])\)大的原象,就是这个数与它前面的数所产生的所有逆序对了。完成这个工作后将树状数组上的\(f(a[k])\)加一。

 

   比如说一串数字(已经离散化)5 2 4 3 1

从左向右遍历

       c[1]    c[2]    c[3]    c[4]    c[5]    sum

插入5:  0       0       0       0       1       0

插入2:  0       1       0       0       0       1 (ask(3,5)=1)

插入4:  0       1       0       1       1       2

插入3:  0       1       1       1       1       4

插入1:  1       1       1       1       1       8

这就是树状数组求逆序对的方法。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using std::pair;
int c[40080];
bool flag[40080];
pair<int,int> a[40080];
bool cmp(pair<int,int> x,pair<int,int> y)
{
    return x.second<y.second;
}
int n;
int lowbit(int x)
{
    return x&(-x);
}
void add(int t,int x)
{
    while(t<=n)
    {
        c[t]+=x;
        t+=lowbit(t);
    }
    return;
}
int ask(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    memset(flag,0,sizeof(flag));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].first);
        a[i].second=i;
    }
    std::sort(a+1,a+1+n);
    a[0].first=0;
    for(int i=1;i<=n;i++)
        if(a[i].first==a[i-1].first)
            flag[i]=true;
    for(int i=1;i<=n;i++)
        if(flag[i])
            a[i].first=a[i-1].first;
        else
            a[i].first=i;
    std::sort(a+1,a+1+n,cmp);
    memset(c,0,sizeof(c));
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        add(a[i].first,1);
        sum+=ask(n)-ask(a[i].first);//求逆序对
    }
    printf("%d\n",sum);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */