神之右大臣 @ 2019-08-02 14:02:36
思路是树状数组+离散化
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[500010];
struct li{
int v;
int s;
}san[500010],hua[500010];
bool cmp(li x,li y)
{
return x.v<y.v;
}
int c[500010];
int lowbit(int x)
{
return x&(-x);
}
void add(int x)
{
while(x<=n){
c[x]+=1;
x+=lowbit(x);
}
}
int read(int x)
{
int res=0;
while(x>0)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
signed main ()
{
cin>>n;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
san[i].v=a[i];
san[i].s=i;
}
sort(san+1,san+1+n,cmp);
for(int i=1;i<=n;i++){
hua[i].s=i;
hua[i].v=san[i].s;
}
sort(hua+1,hua+1+n,cmp);
int ans=0;
for(int i=1;i<=n;i++){
add(hua[i].s);
ans+=(read(n)-read(hua[i].s));
}
cout<<ans;
}
by mendessy @ 2019-08-02 14:12:07
不太看得懂你的离散化,可以再网上搜一下模板