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

求逆序对个数(树状数组)

程序员文章站 2022-05-10 15:13:19
...
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn=100010;
struct node{
    int w;
    int p;
}a[maxn];
int n;
int bit[maxn];

int cmp(node a,node b){
    if(a.w==b.w) return a.p<b.p;
    else return a.w<b.w; 
} 

void update(int i,int x){
    while (i<=n){
        bit[i]+=x;
        i+=i&-i;
    }
}

ll sum(int i){
    ll ans=0;
    while (i){
        ans+=bit[i];
        i-=i&-i;
    }
    return ans;
}

int book[maxn];

int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i].w;
        a[i].p=i;   
    }
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++)
        book[a[i].p]=i;
    long long ans=0;
    for (int i=1;i<=n;i++){
        update(book[i],1);
        ans+=i-sum(book[i]);
    } 
    cout<<ans;
}