题解 P1908 【逆序对】

学无止境 · 2018-11-03 08:37:40 · 题解

好像不少题解都有些古老了，甚至还有误导人的错误的题解存在（深受其害）

因此蒟蒻在这里写一篇新题解，帮助和我一样的蒟蒻理解本题。

Time：2018.11.3

我会说明树状数组与归并排序两种解法，线段树解法与树状数组类似

① 归并排序解法

首先你需要知道什么是归并排序。然后，我们可以这样想：

如果我们想要将一个序列排成从小到大有序的，那么每次划分后合并时左右子区间都是从小到大排好序的，我们只需要统计右边区间每一个数分别会与左边区间产生多少逆序对即可。

不懂的话看栗子：


//在某个时候，左区间：  5 6 7  下标为i
//           右区间：  1 2 9  下标为j
//          
//这个时候我们进行合并：
//step 1：由于 5>1，所以产生了逆序对，这里，我们发现，左区间所有还没有被合并的数都比 1 大，所以1与左区间所有元素共产生了 3 个逆序对(即tot_numleft-i+1对)，统计答案并合并 1 
//step 2：由于 5>2，由上产生了3对逆序对，统计答案并合并 2
//step 3：由于 5<9, 没有逆序对产生，右区间下标 j++
//step 4：由于 6<9, 没有逆序对产生，右区间下标 j++
//step 5：由于 7<9, 没有逆序对产生，右区间下标 j++
//step 6：由于右区间已经结束，正常执行合并左区间剩余，结束

//PS： tot_numleft=3，即左区间总元素个数

看懂了吧(莫名自信)

由于归并排序没有什么坑，正常执行并统计即可，注意 答案会爆 int ！我们需要使用long long存，如果使用 printf 输出，那么可别忘了用%lld ！

复杂度与普通的归并排序相同，为O(Nlog_2N)

效率：1682ms/4.43MB (数据更新之后)

Code：

#include<cstdio>
#include<iostream>
using namespace std;
int n,a[500010],c[500010];
long long ans;

void msort(int b,int e)//归并排序
{
    if(b==e)  
        return;
    int mid=(b+e)/2,i=b,j=mid+1,k=b;
    msort(b,mid),msort(mid+1,e);
    while(i<=mid&&j<=e)
        if(a[i]<=a[j])
            c[k++]=a[i++];
        else
            c[k++]=a[j++],ans+=mid-i+1;//统计答案
    while(i<=mid)
        c[k++]=a[i++];
    while(j<=e)
        c[k++]=a[j++];
    for(int l=b;l<=e;l++)
        a[l]=c[l];
} 

int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    msort(1,n);
    printf("%lld",ans);
    return 0;
}

②树状数组解法

树状数组解法在这道题没有归并快，原因等会说

$Ans1:$ 考虑根据值来建树状数组 , 初始树状数组为全 $0$。现在按照序列从左到右将数据的值对应的位置的数加一，代表又有一个数出现。因此，在循环到第 $i$ 项时，前 $i-1$ 项已经加入到树状数组内了 , 树状数组内比 $a_i$ 大的都会与$a_i$构成逆序对，因为它们一定出现的更早，所以产生的逆序对数量为$i-query(a_i)

注:query(a_i) 代表在树状数组内询问 1 ~ a_i 项的前缀和

$Ans2:$ 确实不够。但是我们需要的只是数据之间的相对大小，只需要满足大于或小于本身，与大多少无关，具体来说，举个栗子： ``` // 1 2 10000 // 1 2 3 //上面两个序列在本题是等效的，因为无论第三项是3还是10000，它都大于第一项和第二项 ``` 这启发我们对数据离散化，先将数据排序，再用 $1$ ~ $n$ 分别对应 $n$ 个数表示它们的相对大小，对新的序列建树状数组空间就够了$(n≤5×10^5)

$Ans3:$ 不处理的话会出错的，问题的关键在于是否有与 $a_i$ 相等的元素在 $a_i$ 前被加入且其相对大小标记更大。出现这种情况就会误将两个相等的数判为逆序对。怎么解决呢，只要所有与 $a_i$ 相等的元素中，先出现的标记也更小就好了(我们只统计相对更大的)。具体只需要在排序时将 $a_i$ 作为第一关键字，下标(第几个出现)作为第二关键字从小到大排序即可。如果用的不是这个方法的树状数组，那么你 $WA$ 也多半是你忘记处理 $Q3$ 中提到的问题了，如果 $RE$ ，多半是空间开小了。同时，再一次，注意 **答案会爆 $int$ ！**我们需要使用**$long$ $long$**存，如果使用 **$printf$** 输出，那么可别忘了用**%$lld$** ！由于我们不仅要排序，还要建树状数组统计，所以，虽然两者复杂度相同，但是树状数组在这里会慢一些。两种方法都是有必要掌握的，数据值域小的时候树状数组会更快，两者均有优点。复杂度瓶颈在排序，为$O(Nlog_2N)

效率:2359ms/8.38MB (数据更新之后)

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int tree[500010],ranks[500010],n;
long long ans; 
struct point
{
    int num,val;
}a[500010];
inline bool cmp(point q,point w)
{
    if(q.val==w.val)
        return q.num<w.num;
    return q.val<w.val;
}
inline void insert(int p,int d)
{
    for(;p<=n;p+=p&-p)
        tree[p]+=d; 
}
inline int query(int p)
{
    int sum=0;
    for(;p;p-=p&-p)
        sum+=tree[p];
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].val),a[i].num=i;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
        ranks[a[i].num]=i;
    for(int i=1;i<=n;i++)
    {
        insert(ranks[i],1);
        ans+=i-query(ranks[i]);
    }
    printf("%lld",ans);
    return 0;
}

如果哪里出锅了请告知我 QWQ

还不懂可以私我