【数状数组求逆序对】
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int Sum,A;
int lowbit(int x){return x&-x;}
void add(int x){for(int i=x;i<=n;i+=lowbit(i))Sum+=1;}
int getsum(int x){int tot=0;for(int i=x;i;i-=lowbit(i))tot+=Sum;return tot;}
int main(){
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&A);
}
for(int i=1;i<=n;i++){
ans+=(getsum(n)-getsum(A));
add(A);
}
printf("%d",ans);
}
页:
[1]