归并RE三个点求助!

P1908 逆序对

lvyijia44 @ 2020-11-07 10:19:25

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;

inline int read(){
    int ans=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        ans=(ans<<3)+(ans<<1)+ch-'0';
        ch=getchar();
    }
    return ans*f;
}
inline void p(ll m){
    printf("%lld",m);
}

int n,a[maxn],rt[maxn];
ll ans;

inline void gb(int l,int r){
    if(l==r)return;
    int m=(l+r)>>1;
    gb(l,m);gb(m+1,r);
    int i=l,j=m+1,cnt=l-1;
    while(i<=m && j<=r){
        if(a[i]<=a[j])
            rt[++cnt]=a[i++];
        else rt[++cnt]=a[j++],ans+=(ll)(m-i+1);
    }
    while(i<=m)
        rt[++cnt]=a[i++];
    while(j<=r)
        rt[++cnt]=a[j++];
    for(int k=l;k<=r;k++)
        a[k]=rt[k];
    return; 
}

int main(){
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();

    gb(1,n);

    p(ans);
    return 0; 
}

by Prean @ 2020-11-07 10:21:15

话说做题的都不会看一眼主页吗。。。


by lvyijia44 @ 2020-11-07 10:23:18

好像还是随机RE,可还行


by Leap_Frog @ 2020-11-07 10:24:28

@lvyijia44 看置顶帖


by 蓝轩宇 @ 2020-11-07 10:26:21

编译器没了


by lvyijia44 @ 2020-11-07 10:28:13

欧,看到了,感谢


|