competitive-programming-library

This documentation is automatically generated by online-judge-verify-helper

View the Project on GitHub kmyk/competitive-programming-library

:warning: old/inversion-number.inc.cpp

Back to top page

Code

ll inversion_number(vector<int> const & a) {
    int n = a.size();
    binary_indexed_tree<plus_monoid> bit(n + 1);
    ll cnt = 0;
    REP (i, n) {
        cnt += i - bit.initial_range_concat(a[i] + 1);
        bit.point_append(a[i], 1);
    }
    return cnt;
}

#line 1 "old/inversion-number.inc.cpp"
ll inversion_number(vector<int> const & a) {
    int n = a.size();
    binary_indexed_tree<plus_monoid> bit(n + 1);
    ll cnt = 0;
    REP (i, n) {
        cnt += i - bit.initial_range_concat(a[i] + 1);
        bit.point_append(a[i], 1);
    }
    return cnt;
}

Back to top page