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