This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "math/inversion_number.hpp"
$0 \leq a_i < n$ であるような数列 $a$ に対して、転倒数を求める。 $O(N\log N)$
数列 $a$ に対して、転倒数を求める。 $O(N\log N)$
#pragma once #include <cassert> #include <limits> #include <vector> #include "../data_structure/compress.hpp" #include "../data_structure/fenwick_tree.hpp" #include "../template/int_alias.hpp" namespace ebi { i64 inversion_number_max_n(const std::vector<int> &a, int n = 200000) { fenwick_tree<i64> fw(n); i64 res = 0; for (auto x : a) { assert(0 <= x && x < n); res += fw.sum(x + 1, n); fw.add(x, 1); } return res; } template <class T> i64 inversion_number(const std::vector<T> &a) { compress<T> cp; for (const auto &x : a) { cp.add(x); } cp.build(); std::vector<int> ca; ca.reserve(a.size()); for (const auto &x : a) { ca.emplace_back(cp.get(x)); } return inversion_number_max_n(ca, cp.size()); } } // namespace ebi
#line 2 "math/inversion_number.hpp" #include <cassert> #include <limits> #include <vector> #line 2 "data_structure/compress.hpp" #include <algorithm> #line 6 "data_structure/compress.hpp" namespace ebi { template <class T> struct compress { private: std::vector<T> cp; public: compress() = default; compress(std::vector<T> cp_) : cp(cp_) { build(); } void build() { std::sort(cp.begin(), cp.end()); cp.erase(std::unique(cp.begin(), cp.end()), cp.end()); } void add(const T &val) { cp.emplace_back(val); } int get(const T &val) const { return std::lower_bound(cp.begin(), cp.end(), val) - cp.begin(); } int size() const { return cp.size(); } bool find(const T &val) const { auto itr = std::lower_bound(cp.begin(), cp.end(), val); if (itr == cp.end()) return false; else return *itr == val; } T val(int idx) const { assert(0 <= idx && idx < (int)cp.size()); return cp[idx]; } }; } // namespace ebi #line 2 "data_structure/fenwick_tree.hpp" #line 5 "data_structure/fenwick_tree.hpp" namespace ebi { template <class T> struct fenwick_tree { private: int n; std::vector<T> data; public: fenwick_tree(int _n) : n(_n), data(std::vector<T>(_n + 1, T(0))) {} void add(int i, T val) { i++; for (int x = i; x <= n; x += x & -x) { data[x] += val; } } T prefix_sum(int i) const { assert(0 <= i && i <= n); T ret = 0; for (int x = i; x > 0; x -= x & -x) { ret += data[x]; } return ret; } T sum(int l, int r) const { return prefix_sum(r) - prefix_sum(l); } T all_sum() const { return prefix_sum(n); } // prefix_sum(x) >= key となる最小のxを返す関数 O(log N) int lower_bound(T key) { if (key <= 0) return 0; int x = 0; int max = 1; while ((max << 1) <= n) max <<= 1; for (int k = max; k > 0; k >>= 1) { if (x + k <= n && data[x + k] < key) { x += k; key -= data[x]; } } return x + 1; } }; } // namespace ebi #line 2 "template/int_alias.hpp" #include <cstdint> namespace ebi { using ld = long double; using std::size_t; using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; } // namespace ebi #line 10 "math/inversion_number.hpp" namespace ebi { i64 inversion_number_max_n(const std::vector<int> &a, int n = 200000) { fenwick_tree<i64> fw(n); i64 res = 0; for (auto x : a) { assert(0 <= x && x < n); res += fw.sum(x + 1, n); fw.add(x, 1); } return res; } template <class T> i64 inversion_number(const std::vector<T> &a) { compress<T> cp; for (const auto &x : a) { cp.add(x); } cp.build(); std::vector<int> ca; ca.reserve(a.size()); for (const auto &x : a) { ca.emplace_back(cp.get(x)); } return inversion_number_max_n(ca, cp.size()); } } // namespace ebi