sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "misc/permutation.hpp"
#pragma once #include <vector> #include "../data-structure/fenwick_tree.hpp" /** * @brief Lexicographic Index of Permutations (in Factorial Number System) */ struct AddMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; std::vector<int> perm_to_num(const std::vector<int>& p) { const int n = p.size(); std::vector<int> num(n); FenwickTree<AddMonoid> ft(n); for (int i = n - 1; i >= 0; --i) { ft.update(p[i], 1); num[n - i - 1] = ft.prefix_fold(p[i]); } return num; } std::vector<int> num_to_perm(const std::vector<int>& num) { const int n = num.size(); std::vector<int> p(n); FenwickTree<AddMonoid> ft(n); for (int i = 0; i < n; ++i) ft.update(i, 1); for (int i = 0; i < n; ++i) { p[i] = ft.lower_bound(num[n - i - 1] + 1); ft.update(p[i], -1); } return p; }
#line 2 "misc/permutation.hpp" #include <vector> #line 2 "data-structure/fenwick_tree.hpp" #include <functional> #line 4 "data-structure/fenwick_tree.hpp" template <typename M> class FenwickTree { using T = M::T; public: FenwickTree() = default; explicit FenwickTree(int n) : n(n), data(n + 1, M::id()) {} T prefix_fold(int i) const { T ret = M::id(); for (; i > 0; i -= i & -i) ret = M::op(ret, data[i]); return ret; } void update(int i, const T& x) { for (++i; i <= n; i += i & -i) data[i] = M::op(data[i], x); } int lower_bound(const T& x) const { return lower_bound(x, std::less<>()); } template <typename Compare> int lower_bound(const T& x, Compare cmp) const { if (!cmp(M::id(), x)) return 0; int k = 1; while (k * 2 <= n) k <<= 1; int i = 0; T v = M::id(); for (; k > 0; k >>= 1) { if (i + k > n) continue; T nv = M::op(v, data[i + k]); if (cmp(nv, x)) { v = nv; i += k; } } return i + 1; } private: int n; std::vector<T> data; }; #line 5 "misc/permutation.hpp" /** * @brief Lexicographic Index of Permutations (in Factorial Number System) */ struct AddMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; std::vector<int> perm_to_num(const std::vector<int>& p) { const int n = p.size(); std::vector<int> num(n); FenwickTree<AddMonoid> ft(n); for (int i = n - 1; i >= 0; --i) { ft.update(p[i], 1); num[n - i - 1] = ft.prefix_fold(p[i]); } return num; } std::vector<int> num_to_perm(const std::vector<int>& num) { const int n = num.size(); std::vector<int> p(n); FenwickTree<AddMonoid> ft(n); for (int i = 0; i < n; ++i) ft.update(i, 1); for (int i = 0; i < n; ++i) { p[i] = ft.lower_bound(num[n - i - 1] + 1); ft.update(p[i], -1); } return p; }