spacecraft__int @ 2021-12-30 19:57:26
#include<bits/stdc++.h>
using namespace std;
int n,m;
int lb(int x){return x&-x;}
long long a[5000005];
int tr[5000005];
int b[5000005],ans;
void add(int x){
while(x<=n){
tr[x]++;
x+=lb(x);
}
return;
}
int sum(int x){
int s=0;
while(x>0){
s+=tr[x];
x-=lb(x);
}
return s;
}
bool cmp(int x,int y){
return a[x]>a[y];
}
int main(){
// freopen("P1908_6.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",a+i);
b[i]=i;
}
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++) add(b[i]),ans+=sum(b[i]-1);
printf("%d",ans);
return 0;
}
by OldVagrant @ 2021-12-30 20:17:43
您这求的是正序对对数,逆序对的话下面那个for循环应该倒序
by OldVagrant @ 2021-12-30 20:23:07
@spacecraft__int
by spacecraft__int @ 2022-01-04 16:07:59
谢谢!