啊啊啊全RE本人已疯,在线等,非常急

P1908 逆序对

youdu666 @ 2022-07-05 18:41:28

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const signed N=500001;
inline int read()
{
    int x=0,y=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-')
            y=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*y;
}
int n,c[N],a[N];
inline int lowbit(int x)
{
    return x&(-x);
}
inline void update(int x,int y)
{
    //y%=mod;
    for(;x<=n;x+=lowbit(x))
    {
        c[x]+=y;
        //c[x]%=mod;
    }
    return;
}
inline int sum(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))
    {
        ans+=c[x];
        //ans%=mod;
    }
    return ans;
}
signed main()
{
    n=read();
    int anss=0;
    for(signed i=1;i<=n;i++)
        a[i]=read();
    for(signed i=1;i<=n;i++)
    {
        anss+=sum(n)-sum(a[i]);
        update(a[i],1);
        //anss%=mod;
    }
    printf("%lld\n",anss);
}

该加的都加了怎么还re


by zenglu @ 2022-07-05 18:44:29

a_i \le 10^9

你的离散化呢?


by expnoi @ 2022-07-05 18:45:38

@youdu666 要离散化


by NastiY_iN_saNitY @ 2022-07-05 19:02:29

楼上正解。


by youdu666 @ 2022-07-05 19:05:17

啊,对哦(刚网断了,再骂一遍路由器)


by youdu666 @ 2022-07-05 19:05:48

谢谢大佬 @expnoi


|