#ifndef VECTOR_INVERSION_NUMBER
#define VECTOR_INVERSION_NUMBER
#include "src/datastructure/fenwick_tree.hpp"
#include "src/vector/coordinate_compression.hpp"
#include <vector>
template<class T>
long long inversion_number(std::vector<T> const &v) {
int const N = v.size();
FenwickTree<int> ft(N);
CoordinateCompression cc(v);
long long res = 0;
for (int i = 0; i < N; ++i) {
int idx = cc.get(v[i]);
res += i - ft.sum(idx);
ft.add(idx, 1);
}
return res;
}
#endif // VECTOR_INVERSION_NUMBER
#line 1 "src/vector/inversion_number.hpp"
#line 1 "src/datastructure/fenwick_tree.hpp"
#include <vector>
template<class T>
class FenwickTree {
private:
int n;
std::vector<T> tree;
public:
FenwickTree(int n) : n(n), tree(n) {}
void add(int i, T x) {
++i;
while (i <= n) {
tree[i - 1] += x;
i += i & -i;
}
}
T sum(int i) { // [0, i)
T s{0};
while (i > 0) {
s += tree[i - 1];
i -= i & -i;
}
return s;
}
T find(int l, int r) { // [l, r)
return sum(r) - sum(l);
}
};
#line 1 "src/vector/coordinate_compression.hpp"
#include <algorithm>
#line 6 "src/vector/coordinate_compression.hpp"
template<class T>
class CoordinateCompression {
private:
std::vector<T> x;
public:
CoordinateCompression(std::vector<T> const &v) : x(v.size()) {
std::partial_sort_copy(v.begin(), v.end(), x.begin(), x.end());
x.erase(std::unique(x.begin(), x.end()), x.end());
}
[[nodiscard]] int size() const { return x.size(); }
T operator[](int k) { return x[k]; }
[[nodiscard]] int get(T const &v) const {
return std::lower_bound(x.begin(), x.end(), v) - x.begin();
}
};
#line 6 "src/vector/inversion_number.hpp"
#line 8 "src/vector/inversion_number.hpp"
template<class T>
long long inversion_number(std::vector<T> const &v) {
int const N = v.size();
FenwickTree<int> ft(N);
CoordinateCompression cc(v);
long long res = 0;
for (int i = 0; i < N; ++i) {
int idx = cc.get(v[i]);
res += i - ft.sum(idx);
ft.add(idx, 1);
}
return res;
}
転倒数 (src/vector/inversion_number.hpp)