欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树状数组求逆序对的个数

程序员文章站 2022-05-10 15:04:38
...
#include <iostream>
#include <cstring>
using namespace std;
#define N 1010
int c[N];
int n;
int lowbit(int i)
{
    return i&(-i);
}
void insert(int i,int x)
{
    for(;i<=n;i+=lowbit(i)){
        c[i]+=x;
    }
}

int getsum(int i)
{
    int sum=0;
    for(;i;i-=lowbit(i)){
        sum+=c[i];
    }
    return sum;
}

int main()
{
    while(cin>>n){
        int ans=0;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            int a;
            cin>>a;
            insert(a,1);
            ans+=i-getsum(a);//统计当前序列中大于a的元素的个数
        }
        cout<<ans<<endl;
    }
    return 0;
}