萌新妹子，求助QAQ

P1908 逆序对

AhoCorasick @ 2019-11-12 08:22:57

#include<bits/stdc++.h>
#define ll long long
const int MAXN=5e5+5;
long long ans;
ll a[MAXN],t[MAXN];
ll n;
inline ll read()
{
    char ch=getchar();
    ll x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}
void merge(ll l,ll r,ll m)
{
    ll i=l,j=m+1;
    ll cnt=0;
    while(i<=m&&j<=r)
    {
        if(a[i]<=a[j])
            t[++cnt]=a[i];
        else
        {
            t[++cnt]=a[j];
            ans+=m-i+1;
        }
    }
    while(i<=m)
        t[++cnt]=a[i];
    while(j<=r)
        t[++cnt]=a[j];
    j=0;
    for(ll i=l;i<=r;i++)
        a[i]=t[++j];
}
void merge_sort(ll l,ll r)
{
    if(l==r)
        return;
    ll mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    merge(l,r,mid);
}
int main()
{
    std::cin>>n;
    for(ll i=1;i<=n;i++)
        a[i]=read();
    merge_sort(1,n);
    std::cout<<ans<<std::endl;
    return 0;
}

为什么会RE，学妹哭唧唧脸\

by Pengsibo @ 2019-11-12 08:53:54

亲，这边建议直接发女装照片呢

额，你的代码有点玄学

merge里面的i要及时++啊

还有cnt的初值不是0

但是这可能不是RE的原因。。

by Pengsibo @ 2019-11-12 08:58:40

正确的归并:

void msort(long long s,long long t)
{
    if(s==t) return;
    long long mid=(s+t)>>1;
    msort(s,mid),msort(mid+1,t);

    long long i=s,j=mid+1,k=s;
    while(i<=mid&&j<=t)
    {
        if(a[i]<=a[j]) r[k++]=a[i++];
        else r[k++]=a[j++],ans+=mid-i+1;
    }

    while(i<=mid) r[k++]=a[i++];
    while(j<=t) r[k++]=a[j++];

    for(register long long h=s;h<=t;h++) a[h]=r[h];
}

by AhoCorasick @ 2019-11-12 12:29:59

@Pengsibo 谢谢

by AhoCorasick @ 2019-11-12 12:31:38

所以为什么会RE呢QAQ

by Pengsibo @ 2019-11-12 16:18:08

不知

by Pengsibo @ 2019-11-12 16:20:38

RE就几种情况

数组开小

数被0除/模

玄学错误

by AhoCorasick @ 2019-11-12 20:30:59

是快读抄挂了嘤嘤嘤QAQ

|