Zarts - 座標圧縮
(lib/00-util/Zarts.cpp)

• View this file on GitHub
• Last update: 2023-05-30 04:32:15+09:00

Zarts

• 座標圧縮

コンストラクタ

• Zarts(const vector & ar, int light_flag = 0, T pre=-1)
• arには座圧したいvectorを渡す。
• light_flag=1のとき、mapを使わずに定数倍の速い座圧を行う。このときkey,valを逆変換するmapは生成されない。
• light_flag=1のときは比較ベースで座圧する。preの値はarに含まれない最小の値を渡す必要がある。(任意のar[i]に関して pre < a[i] が成り立つ必要がある)
• 計算量 $O(N\log N)$

メソッド

• 座圧した配列に関しては、compressedはpublicメンバなので、直接アクセスして使用する
• T get_value(int key)
  • key番目に大きい値を返す
  • $O(1)$
• int get_key(T value)
  • valueが座圧後何番目に大きいかのkeyを返す
  • $O(\log N)$
• size_t size()
  • 座圧後の値の種類数を返す
  • $O(1)$

Verified with

• test/util/Zarts.test.cpp

Code

/*
 * @title Zarts - 座標圧縮
 * @docs md/util/Zarts.md
 */
template<class T> class Zarts{
    vector<T> value;
    map<T,int> key;
    size_t sz;
public:
    vector<int> compressed;
    Zarts(const vector<T> & ar, int light_flag = 0, T pre=-1) : compressed(ar.size()) {
        if(!light_flag) {
            for (auto &e : ar) key[e];
            int cnt=0;
            for (auto &e : key) e.second = cnt++;
            for (int i=0;i<ar.size();++i) compressed[i]=key[ar[i]];
            value.resize(key.size());
            for (auto &e : key) value[e.second] = e.first;
            sz = cnt;
        }
        else {
            vector<pair<int,int>> ord(ar.size());
            for(int i=0;i<ar.size();++i) ord[i]={ar[i],i};
            sort(ord.begin(),ord.end());
            int cnt=-1;
            for(int i=0;i<ar.size();++i) {
                if(pre < ord[i].first) cnt++;
                compressed[ord[i].second] = cnt;
                pre = ord[i].first;
            }
            sz = cnt+1;
        }
    }
    T get_value(int key) {
        return value[key];
    }
    int get_key(T value) {
        assert(key.count(value));
        return key[value];
    }
    size_t size() {
        return sz;
    }
};

#line 1 "lib/00-util/Zarts.cpp"
/*
 * @title Zarts - 座標圧縮
 * @docs md/util/Zarts.md
 */
template<class T> class Zarts{
    vector<T> value;
    map<T,int> key;
    size_t sz;
public:
    vector<int> compressed;
    Zarts(const vector<T> & ar, int light_flag = 0, T pre=-1) : compressed(ar.size()) {
        if(!light_flag) {
            for (auto &e : ar) key[e];
            int cnt=0;
            for (auto &e : key) e.second = cnt++;
            for (int i=0;i<ar.size();++i) compressed[i]=key[ar[i]];
            value.resize(key.size());
            for (auto &e : key) value[e.second] = e.first;
            sz = cnt;
        }
        else {
            vector<pair<int,int>> ord(ar.size());
            for(int i=0;i<ar.size();++i) ord[i]={ar[i],i};
            sort(ord.begin(),ord.end());
            int cnt=-1;
            for(int i=0;i<ar.size();++i) {
                if(pre < ord[i].first) cnt++;
                compressed[ord[i].second] = cnt;
                pre = ord[i].first;
            }
            sz = cnt+1;
        }
    }
    T get_value(int key) {
        return value[key];
    }
    int get_key(T value) {
        assert(key.count(value));
        return key[value];
    }
    size_t size() {
        return sz;
    }
};

Back to top page