【归并排序】P1908 全WA求助

sunyizhe @ 2023-07-10 21:00:21

by sunyizhe @ 2023-07-10 21:00:36

//程序算法：归并排序
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N],c[N],n;
long long cnt;

void fast_read()
{
    ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
}

void merge(int l1,int r1,int l2,int r2)
{
    int i=l1,j=l2,k=l1;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<=a[j])c[k++]=a[i++];
        else c[k++]=a[j++],cnt+=(long long)r1-i+1;
    }

    while(i<=r1)c[k++]=a[i++];
    while(j<=r2)c[k++]=a[j++];

    for(int x=l1;x<=l2;x++)
        a[x]=c[x];
}

void merge_sort(int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)>>1;
        merge_sort(l,mid),merge_sort(mid+1,r);

        merge(l,mid,mid+1,r);
    }
}

int main()
{
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);

    fast_read();

    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    merge_sort(1,n);

    cout<<cnt<<endl;
    return 0;
}

by sunyizhe @ 2023-07-10 21:24:53

破案了，merge 函数里面最后赋值的 for 语句的 r2 打成了 l2。

当作警示后人罢。本贴完结。