座標圧縮 (lib/algorithm/compress.hpp)

• View this file on GitHub
• Last update: 2025-06-20 15:18:35+09:00
• Include: #include "lib/algorithm/compress.hpp"

Required by

• 転倒数 (lib/algorithm/inversion_number.hpp)
• ウェーブレット行列 (lib/data_structure/compressed_wavelet_matrix.hpp)
• 要素を特定のキー（条件）でフィルタリングして区間取得を行えるセグメント木 (lib/segtree/filtered_segment_tree.hpp)

Verified with

• test/aoj/alds1/inversion_number.test.cpp
• test/aoj/challenge/2270.test.cpp
• test/aoj/challenge/2426.1.test.cpp
• test/yosupo/data_structure/range_kth_smallest.test.cpp
• test/yosupo/data_structure/static_range_frequency.test.cpp
• test/yosupo/data_structure/static_range_inversions.test.cpp
• test/yosupo/math/number_of_subsequences.test.cpp
• test/yukicoder/0618.test.cpp
• test/yukicoder/1209.test.cpp

Code

#pragma once
#include <algorithm>
#include <iterator>
#include <vector>

/// @brief 座標圧縮
template <class T>
struct coordinate_compression {
    coordinate_compression() = default;
    coordinate_compression(const std::vector<T> &_data) : data(_data) { build(); }

    const T &operator[](int i) const { return data[i]; }
    T front() const { return data.front(); }
    T back() const { return data.back(); }

    void add(T x) { data.emplace_back(x); }

    void build() {
        std::sort(data.begin(), data.end());
        data.erase(std::unique(data.begin(), data.end()), data.end());
    }

    bool exists(T x) const {
        auto it = std::lower_bound(data.begin(), data.end(), x);
        return it != data.end() && *it == x;
    }

    int get(T x) const { return std::distance(data.begin(), std::lower_bound(data.begin(), data.end(), x)); }
    int lower_bound(T x) const { return std::distance(data.begin(), std::lower_bound(data.begin(), data.end(), x)); }
    int upper_bound(T x) const { return std::distance(data.begin(), std::upper_bound(data.begin(), data.end(), x)); }

    std::vector<int> compress(const std::vector<T> &v) const {
        int n = v.size();
        std::vector<int> res(n);
        for (int i = 0; i < n; ++i) res[i] = get(v[i]);
        return res;
    }

    int size() const { return data.size(); }

  private:
    std::vector<T> data;
};

/// @brief 座標圧縮
template <class T>
std::vector<int> compress(const std::vector<T> &v) {
    coordinate_compression cps(v);
    std::vector<int> res;
    res.reserve(std::size(v));
    for (auto &&x : v) res.emplace_back(cps.get(x));
    return res;
}

#line 2 "lib/algorithm/compress.hpp"
#include <algorithm>
#include <iterator>
#include <vector>

/// @brief 座標圧縮
template <class T>
struct coordinate_compression {
    coordinate_compression() = default;
    coordinate_compression(const std::vector<T> &_data) : data(_data) { build(); }

    const T &operator[](int i) const { return data[i]; }
    T front() const { return data.front(); }
    T back() const { return data.back(); }

    void add(T x) { data.emplace_back(x); }

    void build() {
        std::sort(data.begin(), data.end());
        data.erase(std::unique(data.begin(), data.end()), data.end());
    }

    bool exists(T x) const {
        auto it = std::lower_bound(data.begin(), data.end(), x);
        return it != data.end() && *it == x;
    }

    int get(T x) const { return std::distance(data.begin(), std::lower_bound(data.begin(), data.end(), x)); }
    int lower_bound(T x) const { return std::distance(data.begin(), std::lower_bound(data.begin(), data.end(), x)); }
    int upper_bound(T x) const { return std::distance(data.begin(), std::upper_bound(data.begin(), data.end(), x)); }

    std::vector<int> compress(const std::vector<T> &v) const {
        int n = v.size();
        std::vector<int> res(n);
        for (int i = 0; i < n; ++i) res[i] = get(v[i]);
        return res;
    }

    int size() const { return data.size(); }

  private:
    std::vector<T> data;
};

/// @brief 座標圧縮
template <class T>
std::vector<int> compress(const std::vector<T> &v) {
    coordinate_compression cps(v);
    std::vector<int> res;
    res.reserve(std::size(v));
    for (auto &&x : v) res.emplace_back(cps.get(x));
    return res;
}

Back to top page