关于归并排序做法的疑问

KDL_ANIPLEX @ 2024-05-27 21:22:25

#include<bits/stdc++.h>
using namespace std;
int n;
long long s;
int a[500010];
int d[500010];
void so(int l,int r){
    int fd=(l+r)/2;
    if (l==r)
        return;
    else{
        so(l,fd);
        so(fd+1,r);
    }
    int lt=l,rt=fd+1,dn=0;
    while (lt<=fd&&rt<=r){
        if (a[lt]>a[rt])
            s=s+fd-lt+1,d[++dn]=a[rt++];/*
            为什么是s=s+fd-lt+1,
            而s=s+rt-fd+1不行
            即：
            如果a[lt]>a[rt]
            则a[lt]与a[fd+1至rt]均为逆序对
            为什么不行
            */
        else
            d[++dn]=a[lt++];
    }
    while (lt<=fd) d[++dn]=a[lt++];
    while (rt<=r) d[++dn]=a[rt++];
    for (int i=l;i<=r;i++)
    a[i]=d[i-l+1];
    return;
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++)
    cin>>a[i];
    so(1,n);
    printf("%lld\n",s);
    return 0;
} 

by vflower @ 2024-05-27 21:36:13

@KDL_ANIPLEX fd-lt+1 这样计数是不重不漏的，而 rt-fd+1 这样既有重复的情况也有漏的情况，比如连续的左边大于右边就是重，连续的右边大于左边就是漏，其实可以把计数和归并分开做，这样能清晰一些

by vflower @ 2024-05-27 21:36:52

而且是不是应该是 rt-fd（

by SakurajiamaMai @ 2024-05-27 21:52:16

@vflower 为什么会重？

by vflower @ 2024-05-27 22:05:16

@SakurajiamaMai 刚才确实没想清楚，但是漏的情况确实有吧

by vflower @ 2024-05-27 22:16:35

10 10 10 10
1 2 3 4

这样就会少，反正只改 s=s+fd-lt+1 肯定是不行，我是计数菜b我不会，还是建议计数和合并分开进行

by KDL_ANIPLEX @ 2024-05-28 20:30:12

@vflower 懂了，谢谢

by SakurajiamaMai @ 2024-05-28 21:14:32

@KDL_ANIPLEX 你可以修改一下,就按着你的做法,在最后更新,也就是更新L的地方,再更新一下答案就好了,这样就不会漏了,有篇博客讲过,这里给你个链接,最好先自己尝试下

点这里

by SakurajiamaMai @ 2024-05-28 21:16:08

@vflower 对的，这样是会漏，P8613这道题就计算的很清楚

by SXqwq @ 2024-06-18 16:31:00

@SakurajiamaMai

举个例子： 6 7 8 9 1 2 3 4

当 rt=6,lt=1 时，应该是新增 4 个逆序对，因为 2 分别和 6,7,8,9 构成逆序对。但是 rt-lt+1 会错误地把 (1,2) 认为是逆序对。

认为是 rt-lt+1 的估计是随手搓了个小样例吧（