This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#include "dp/inversion_number.hpp"
$ O(N \log N) $ で転倒数を求める。 座圧する。 転倒数はバブルソートの交換回数と等しい。
#pragma once #include "data_structure/fenwick_tree.hpp" template <class T> long long inversion_number(std::vector<T>& A) { auto B = A; sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end()); int N = (int)B.size(); FenwickTree<int> fen(N); long long ret = 0; for (auto& ai : A) { int i = lower_bound(B.begin(), B.end(), ai) - B.begin(); ret += fen.sum(i + 1, N); fen.add(i, 1); } return ret; }
#line 2 "dp/inversion_number.hpp" #line 2 "data_structure/fenwick_tree.hpp" template <class T> struct FenwickTree { int n; std::vector<T> seg; FenwickTree() : n(0) {} FenwickTree(int n) : n(n), seg(n + 1, 0) {} FenwickTree(std::vector<T>& arr) { n = int(arr.size()); seg.resize(n + 1); for (int i = 0; i < n; i++) add(i, arr[i]); } // A[i] += x void add(int i, const T& x) { assert(0 <= i and i < n); i++; // 1-indexed while (i <= n) { seg[i] += x; i += i & -i; } } // A[0] + ... + A[i - 1] T sum(int i) const { assert(0 <= i and i <= n); T s = T(0); while (i > 0) { s += seg[i]; i -= i & -i; } return s; } // A[a] + ... + A[b - 1] T sum(int a, int b) const { assert(0 <= a and a <= b and b <= n); return sum(b) - sum(a); } // return A[i] T get(int i) const { return sum(i, i + 1); } // A[i] = x void set(int i, const T x) { add(i, x - get(i)); } // output friend std::ostream& operator<<(std::ostream& os, const FenwickTree& fen) { for (int i = 0; i < fen.n; i++) os << fen.get(i) << " \n"[i == fen.n - 1]; return os; } }; #line 4 "dp/inversion_number.hpp" template <class T> long long inversion_number(std::vector<T>& A) { auto B = A; sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end()); int N = (int)B.size(); FenwickTree<int> fen(N); long long ret = 0; for (auto& ai : A) { int i = lower_bound(B.begin(), B.end(), ai) - B.begin(); ret += fen.sum(i + 1, N); fen.add(i, 1); } return ret; }