love 发表于 2018-6-14 14:01:04

【数状数组求逆序对】


#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]
查看完整版本: 【数状数组求逆序对】