This documentation is automatically generated by online-judge-tools/verification-helper
#include "../Misc/compress.h"
#include "../DataStructure/Fenwick/Fenwick.h"
// Given vector vs, return number of inversions
template<typename T>
long long count_inversions(vector<T> vs) {
int n = vs.size();
auto compressor = CompressorBuilder<T>{vs}.build();
compressor.compress_inplace(vs);
Fenwick<int> bit(n);
long long res = 0;
for (auto v : vs) {
res += bit.get(v+1, n);
bit.update(v, +1);
}
return res;
}
#line 1 "Misc/compress.h"
// Compressor {{{
/* Example usage:
auto compressor = CompressorBuilder<T>{vs}.build();
int x = compessor.must_eq(vs[0]);
compressor.compress_inplace(vs);
*/
// Based on https://suisen-cp.github.io/cp-library-cpp/library/util/coordinate_compressor.hpp
template<typename T>
struct CompressorBuilder {
// Do not use directly. Use builder.build()
struct Compressor {
// Number of unique keys
int size() const { return xs.size(); }
void compress_inplace(std::vector<T>& vals) {
for (int& val : vals) {
val = must_eq(val);
}
}
[[nodiscard]] std::vector<T> compress(const std::vector<T>& vals) {
std::vector<T> res(vals.size());
for (int i = 0; i < static_cast<int> (res.size()); ++i) {
res[i] = must_eq(vals[i]);
}
return res;
}
bool has_key(const T& key) const {
return std::binary_search(xs.begin(), xs.end(), key);
}
#define LB(key) std::lower_bound(xs.begin(), xs.end(), key)
#define UB(key) std::upper_bound(xs.begin(), xs.end(), key)
std::optional<int> eq(const T& key) {
auto it = LB(key);
return it == xs.end() ? std::nullopt : std::optional<int>{it - xs.begin()};
}
std::optional<int> geq(const T& key) {
auto it = LB(key);
return it == xs.end() ? std::nullopt : std::optional<int>{it - xs.begin()};
}
std::optional<int> gt(const T& key) {
auto it = UB(key);
return it == xs.end() ? std::nullopt : std::optional<int>{it - xs.begin()};
}
std::optional<int> leq(const T& key) {
auto it = UB(key);
return it == xs.begin() ? std::nullopt : std::optional<int>{it - xs.begin() - 1};
}
std::optional<int> lt(const T& key) {
auto it = LB(key);
return it == xs.begin() ? std::nullopt : std::optional<int>{it - xs.begin() - 1};
}
// throw exception if no such key is found
int must_eq(const T& key) {
auto it = LB(key);
assert(it != xs.end());
return it - xs.begin();
}
// throw exception if no such key is found
int must_geq(const T& key) {
auto it = LB(key);
assert(it != xs.end());
return it - xs.begin();
}
// throw exception if no such key is found
int must_gt(const T& key) {
auto it = UB(key);
assert(it != xs.end());
return it - xs.begin();
}
// throw exception if no such key is found
int must_leq(const T& key) {
auto it = UB(key);
assert(it != xs.begin());
return it - xs.begin() - 1;
}
// throw exception if no such key is found
int must_lt(const T& key) {
auto it = LB(key);
assert(it != xs.begin());
return it - xs.begin() - 1;
}
#undef LB
#undef UB
std::vector<T> xs;
};
auto build() {
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
return Compressor{xs};
}
void add(const T& key) { xs.push_back(key); }
void add(T&& key) { xs.push_back(std::move(key)); }
std::vector<T> xs;
};
// }}}
#line 1 "DataStructure/Fenwick/Fenwick.h"
// 1D Fenwick {{{
// 0 based index
//
// Tested:
// - https://judge.yosupo.jp/problem/static_range_sum
// - https://judge.yosupo.jp/problem/point_add_range_sum
template<
typename T // need to support operators + -
> struct Fenwick {
Fenwick(int _n) : n(_n), f(_n + 1) {}
// a[u] += val
void update(int u, T val) {
assert(0 <= u && u < n);
++u;
for (; u <= n; u += u & -u) {
f[u] += val;
}
}
// return a[0] + .. + a[u-1]
T get(int u) const {
assert(0 <= u && u <= n);
T res = 0;
for (; u > 0; u -= u & -u) {
res += f[u];
}
return res;
}
// return a[l] + .. + a[r-1]
T get(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) return 0; // empty
return get(r) - get(l);
}
void reset() {
std::fill(f.begin(), f.end(), T(0));
}
int n;
vector<T> f;
};
// }}}
#line 3 "DP/count_inversions.h"
// Given vector vs, return number of inversions
template<typename T>
long long count_inversions(vector<T> vs) {
int n = vs.size();
auto compressor = CompressorBuilder<T>{vs}.build();
compressor.compress_inplace(vs);
Fenwick<int> bit(n);
long long res = 0;
for (auto v : vs) {
res += bit.get(v+1, n);
bit.update(v, +1);
}
return res;
}