【数状数组求逆序对】 - 重工电子论坛

[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+=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);

}