归并排序做但是超时，该怎么改？？？

P1908 逆序对

肖睿航 @ 2021-05-08 13:20:15

这是我第一次的逆序对，但感觉没什么错误，请各位帮我大佬康康

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,s1[500050],s2[500020],cnt;
void merge(int L,int  R,int Mid){
    long long i = L,j = Mid + 1,k = L;
    while(i <= Mid && j <= R){
        if(s1[i] <= s1[j])s2[k ++]=s1[i ++];
        else{
             cnt += Mid - i + 1; 
             s2[k ++] = s1[j ++];
        } 
    }
    while(i <= Mid)s2[k ++] = s1[i ++];
    while(j <= R)s2[k ++] = s1[j ++];
    for(int i=L; i<=R; i++)s1[i] = s2[i];
}
void mergesort(int L,int R){
    if(L<R){
        long long Mid = (L + R) / 2;
        mergesort(1,Mid);mergesort(Mid+1,R);
        merge(L,R,Mid);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d",&s1[i]);
    mergesort(1,n);
    printf("%d ",cnt);
    return 0;
}

by 肖睿航 @ 2021-05-08 13:22:10

个人感觉只是照着模板打，不知如何优化...在下萌新，勿喷

by 肖睿航 @ 2021-05-08 13:35:32

听了一位大佬同学的建议，用了快读快写但还是错了。。。。。（原因超时）

【时间限制1.00s】

【用时24.00s】

by 信守天下 @ 2021-05-08 13:44:50

序列中每个数字不超过 10^9 。

所以为什么要 long long

by 信守天下 @ 2021-05-08 13:45:27

int 比 long long 快

by le0n @ 2021-05-08 14:02:02

void mergesort(int L,int R){
    if(L<R){
        long long Mid = (L + R) / 2;
        mergesort(1,Mid);mergesort(Mid+1,R);
        merge(L,R,Mid);
    }
}

您的第一个mergesort里是不是应该填mergesort(L,Mid)?

by le0n @ 2021-05-08 14:02:34

long long Mid下面的那一行

by stansten @ 2021-05-08 19:39:40

楼上说的对，改一下L，然后改一下格式化输入输出的问题，数据类型匹配了就过了

#include<bits/stdc++.h>
using namespace std;
int n,s1[500050],s2[500020];
long long cnt;
void merge(int L,int  R,int Mid){
    long long i = L,j = Mid + 1,k = L;
    while(i <= Mid && j <= R){
        if(s1[i] <= s1[j])s2[k ++]=s1[i ++];
        else{
             cnt += Mid - i + 1; 
             s2[k ++] = s1[j ++];
        } 
    }
    while(i <= Mid)s2[k ++] = s1[i ++];
    while(j <= R)s2[k ++] = s1[j ++];
    for(int i=L; i<=R; i++)s1[i] = s2[i];
}
void mergesort(int L,int R){
    if(L<R){
        long long Mid = (L + R) / 2;
        mergesort(L,Mid);mergesort(Mid+1,R);
        merge(L,R,Mid);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d",&s1[i]);
    mergesort(1,n);
    printf("%lld",cnt);
    return 0;
}