喵の耳 @ 2019-04-06 09:43:27
ORZ
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],c[1000005],b[1000005];
void add(int x,int y){
for(;x<=n;x+=x&-x)c[x]+=y;
}
int ask(int x){
int ans=0;
for(;x;x-=x&-x)ans+=c[x];
return ans;
}
bool cmp(int x,int y){
return a[x]>a[y];
}
int main(){
int ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,c[i]);
b[i]=i;
}
sort(a+1,a+n+1,cmp);
for(int i=n;i>=1;i--){
ans+=ask(b[i]-1);
add(b[i],1);
}
printf("%d",ans);
return 0;
}
by aminoas @ 2019-04-06 09:57:30
用树状数组做逆序对?!