【数状数组求逆序对】

love

[AppleScript] syntaxhighlighter_viewsource syntaxhighlighter_copycode

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int Sum[1000],A[1000];
int lowbit(int x){return x&-x;}
void add(int x){for(int i=x;i<=n;i+=lowbit(i))Sum[i]+=1;}
int getsum(int x){int tot=0;for(int i=x;i;i-=lowbit(i))tot+=Sum[i];return tot;}
int main(){
	int ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]);
	}
	for(int i=1;i<=n;i++){
		ans+=(getsum(n)-getsum(A[i]));
		add(A[i]);
	}
	printf("%d",ans);
}