全部RE,可是对样例了啊QwQ,本蒟蒻要崩溃了,求各位大佬帮助

P1908 逆序对

I_LOVE_XYN @ 2024-02-17 17:22:04

#include<iostream>
#define int long long
using namespace std;
int a[500005],b[500005],ans,n;
int lowbit(int x) {return (x&(-x));}
void upload(int p) {for(int i=p;i<=500005; i+=lowbit(i))a[i]++;}
int getsum(int x) {
    int sum=0;
    for(int i=x; i; i-=lowbit(i))sum+=a[i];
    return sum;
}
signed main() {
    scanf("%lld",&n);
    for(int i=1; i<=n; i++) scanf("%lld",&b[i]);
    for(int i=1; i<=n; i++) {
        upload(b[i]);
        ans+=i-getsum(b[i]);
    }
    printf("%lld",ans);
}

by lizicheng3042 @ 2024-02-17 17:28:04

没有 return 0;啊……


by billtun @ 2024-02-17 17:34:14

e

你第6行不能枚举到500005呀


by No0Chenquanlin @ 2024-02-17 17:34:19

你看你数组开到了多少,用了多少。。。


by remake1958 @ 2024-02-19 01:14:02

你这应该是o(n^2)的渐近时间复杂度,肯定超时,这题得要log(n)才行,最重要的是,你的ans没有定义为long long类型,虽然你输出的是longlong类型


by remake1958 @ 2024-02-19 01:16:19

你用归并排序就肯定能过,我就是这样过的


by I_LOVE_XYN @ 2024-02-19 11:22:23

感谢各位大佬的帮助


by I_LOVE_XYN @ 2024-02-19 11:24:27

@remake1958 好吧,还以为自己能搓出树状数组的,高估自己了QwQ


|