number/inversion_number.hpp

View this file on GitHub
Last update: 2021-08-30 04:35:37+09:00
Include: #include "number/inversion_number.hpp"

Depends on

Code

#pragma once
#include <cstdint>
#include <vector>
#include "../data_structure/binary_indexed_tree.hpp"
#include "../utils/macros.hpp"
#include "../monoids/plus.hpp"

int64_t inversion_number(const std::vector<int> &a) {
    int n = a.size();
    binary_indexed_tree<plus_monoid<int64_t>> bit(n + 1);
    int64_t cnt = 0;
    REP (i, n) {
        cnt += i - bit.initial_range_get(a[i] + 1);
        bit.point_mult(a[i], 1);
    }
    return cnt;
}

#line 2 "number/inversion_number.hpp"
#include <cstdint>
#include <vector>
#line 2 "data_structure/binary_indexed_tree.hpp"
#include <cassert>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 5 "data_structure/binary_indexed_tree.hpp"

/**
 * @brief Binary Indexed Tree
 */
template <typename CommutativeMonoid>
struct binary_indexed_tree {
    typedef typename CommutativeMonoid::value_type value_type;
    CommutativeMonoid mon;
    std::vector<value_type> data;
    binary_indexed_tree(int n, CommutativeMonoid const & mon_ = CommutativeMonoid())
            : mon(mon_),
              data(n, mon.unit()) {
    }
    template <class InputIterator>
    binary_indexed_tree(InputIterator first, InputIterator last, CommutativeMonoid const & mon_ = CommutativeMonoid())
            : mon(mon_),
              data(first, last) {
        REP3 (j, 1, data.size() + 1) {
            int k = j + (j & -j);
            if (k - 1 < static_cast<int>(data.size())) {
                data[k - 1] = mon.mult(data[k - 1], data[j - 1]);
            }
        }
    }
    /**
     * @note $a_i \gets a_i + z$
     * @note $O(\log N)$
     */
    void point_mult(int i, value_type z) {
        assert (0 <= i and i < static_cast<int>(data.size()));
        for (int j = i + 1; j <= static_cast<int>(data.size()); j += j & -j) {
            data[j - 1] = mon.mult(data[j - 1], z);
        }
    }
    /**
     * @note $\sum _ {i \lt r} a_i$
     * @note $O(\log N)$
     */
    value_type initial_range_get(int r) {
        assert (0 <= r and r <= static_cast<int>(data.size()));
        value_type acc = mon.unit();
        for (int i = r; 0 < i; i -= i & -i) {
            acc = mon.mult(data[i - 1], acc);
        }
        return acc;
    }
};
#line 2 "monoids/plus.hpp"

template <class T>
struct plus_monoid {
    typedef T value_type;
    value_type unit() const { return value_type(); }
    value_type mult(value_type a, value_type b) const { return a + b; }
};
#line 7 "number/inversion_number.hpp"

int64_t inversion_number(const std::vector<int> &a) {
    int n = a.size();
    binary_indexed_tree<plus_monoid<int64_t>> bit(n + 1);
    int64_t cnt = 0;
    REP (i, n) {
        cnt += i - bit.initial_range_get(a[i] + 1);
        bit.point_mult(a[i], 1);
    }
    return cnt;
}