座標圧縮
(util/compress.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "util/compress.hpp"

概要

座標圧縮.

計算量

$O(n\log n)$

使用例

• auto [com, rev] = compress(ord) : ordを座標圧縮.
  • com : 座標圧縮して得られる配列.
  • rev : ordとcomの対応関係.

Code

/**
* @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);
}

Back to top page