This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub morioprog/cpplib
#include "util/compress.hpp"
座標圧縮.
$O(n\log n)$
auto [com, rev] = compress(ord)
ord
com
rev
/** * @brief 座標圧縮 * @docs docs/util/compress.md */ template <typename T> pair<vector<T>, map<T, int>> compress(vector<T> ord) { vector<T> com(ord); map<T, int> rev; sort(com.begin(), com.end()); com.erase(unique(com.begin(), com.end()), com.end()); for (int i = 0; i < com.size(); ++i) rev[com[i]] = i; vector<T> ret; for (auto& e : ord) ret.emplace_back(rev[e]); return make_pair(ret, rev); }
#line 1 "util/compress.hpp" /** * @brief 座標圧縮 * @docs docs/util/compress.md */ template <typename T> pair<vector<T>, map<T, int>> compress(vector<T> ord) { vector<T> com(ord); map<T, int> rev; sort(com.begin(), com.end()); com.erase(unique(com.begin(), com.end()), com.end()); for (int i = 0; i < com.size(); ++i) rev[com[i]] = i; vector<T> ret; for (auto& e : ord) ret.emplace_back(rev[e]); return make_pair(ret, rev); }