C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title その他/転倒数 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D */ #include <iostream> #include <vector> #include "emthrm/misc/inversion_number.hpp" int main() { int n; std::cin >> n; std::vector<int> a(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } std::cout << emthrm::inversion_number(a) << '\n'; return 0; }
#line 1 "test/misc/inversion_number.test.cpp" /* * @title その他/転倒数 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D */ #include <iostream> #include <vector> #line 1 "include/emthrm/misc/inversion_number.hpp" #include <algorithm> #include <iterator> #line 7 "include/emthrm/misc/inversion_number.hpp" #line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp" #include <bit> #line 6 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp" namespace emthrm { template <typename Abelian> struct FenwickTree { explicit FenwickTree(const int n, const Abelian ID = 0) : n(n), ID(ID), data(n, ID) {} void add(int idx, const Abelian val) { for (; idx < n; idx |= idx + 1) { data[idx] += val; } } Abelian sum(int idx) const { Abelian res = ID; for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) { res += data[idx]; } return res; } Abelian sum(const int left, const int right) const { return left < right ? sum(right) - sum(left) : ID; } Abelian operator[](const int idx) const { return sum(idx, idx + 1); } int lower_bound(Abelian val) const { if (val <= ID) [[unlikely]] return 0; int res = 0; for (int mask = std::bit_ceil(static_cast<unsigned int>(n + 1)) >> 1; mask > 0; mask >>= 1) { const int idx = res + mask - 1; if (idx < n && data[idx] < val) { val -= data[idx]; res += mask; } } return res; } private: const int n; const Abelian ID; std::vector<Abelian> data; }; } // namespace emthrm #line 9 "include/emthrm/misc/inversion_number.hpp" namespace emthrm { template <typename T> long long inversion_number(const std::vector<T>& a) { const int n = a.size(); std::vector<T> b = a; std::sort(b.begin(), b.end()); b.erase(std::unique(b.begin(), b.end()), b.end()); FenwickTree<int> bit(b.size()); long long res = 0; for (int i = 0; i < n; ++i) { const int idx = std::distance( b.begin(), std::lower_bound(b.begin(), b.end(), a[i])); res += i - bit.sum(idx + 1); bit.add(idx, 1); } return res; } } // namespace emthrm #line 11 "test/misc/inversion_number.test.cpp" int main() { int n; std::cin >> n; std::vector<int> a(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } std::cout << emthrm::inversion_number(a) << '\n'; return 0; }