Inversion Number (転倒数)
(DP/InversionNumber.hpp)

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "DP/InversionNumber.hpp"

概要

転倒数を返す
中でBinary Indexed Treeの処理をしている

計算量

配列の長さをNとしたとき，O(N logN)

Verified with

• test/AOJ_ALDS1_5_D.test.cpp

Code

template<typename T>
long long InversionNumber(vector<T> v){
    vector<T> ord=v;
    sort(begin(ord),end(ord));
    ord.erase(unique(begin(ord),end(ord)),end(ord));
    vector<long long> bit(ord.size()+1,0);
    long long ret=0;
    for(int i=0;i<(int)v.size();i++){
        int p=lower_bound(begin(ord),end(ord),v[i])-begin(ord)+1;
        for(int j=p;j;j-=(j&-j)) ret-=bit[j];
        for(int j=p;j<=(int)ord.size();j+=(j&-j)) bit[j]+=1;
        ret+=i;
    } 
    return ret;
}

#line 1 "DP/InversionNumber.hpp"
template<typename T>
long long InversionNumber(vector<T> v){
    vector<T> ord=v;
    sort(begin(ord),end(ord));
    ord.erase(unique(begin(ord),end(ord)),end(ord));
    vector<long long> bit(ord.size()+1,0);
    long long ret=0;
    for(int i=0;i<(int)v.size();i++){
        int p=lower_bound(begin(ord),end(ord),v[i])-begin(ord)+1;
        for(int j=p;j;j-=(j&-j)) ret-=bit[j];
        for(int j=p;j<=(int)ord.size();j+=(j&-j)) bit[j]+=1;
        ret+=i;
    } 
    return ret;
}

Back to top page