上官书房 @ 2019-08-31 21:51:01
#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,也就是
by X_WT @ 2019-08-31 23:18:17
李三花
by 上官书房 @ 2019-09-01 11:04:10