全RE怎么办? qwq

P1908 逆序对

上官书房 @ 2019-08-31 21:51:01

呜呜呜┭┮﹏┭┮

为什么全RE呀??

#include<bits/stdc++.h>
using namespace std;
long long n,ans,mmax,a[500001],c[500001];

long long lowbit(long long d)
{
    return d&(-d);
}

void insert(long long d,long long x)
{
    while(d<=mmax)
    {
        c[d]+=x;
        d+=lowbit(d);
    }
}

long long getsum(long long d)
{
    long long res=0;
    while(d!=0)
    {
        res+=c[d];
        d-=lowbit(d);
    }
    return res;
}

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        mmax=max(mmax,a[i]);
    }
    for(int i=1;i<=n;++i)
        insert(a[i],1);
    for(int i=1;i<=n;++i)
    {
        insert(a[i],-1);
        ans+=getsum(a[i]);
        //printf("%lld ",getsum(a[i]));
    }
    printf("%lld\n",ans);
    return 0;
}

by yqaty @ 2019-08-31 22:19:09

@上官书房

离散化啊。。。。


by GKxx @ 2019-08-31 22:59:07

@上官书房 树状数组的下标最大到mmax,也就是a_i的最大值,而a_i是可以到10^9


by X_WT @ 2019-08-31 23:18:17

李三花


by 上官书房 @ 2019-09-01 11:04:10

哦~

谢啦 Thanks♪(・ω・)ノ


|