Compression (座標圧縮)
(lib/others/compression.hpp)

• View this file on GitHub
• Last update: 2025-01-09 22:07:23+09:00
• Include: #include "lib/others/compression.hpp"

Compression (座標圧縮)

使い方

• compress<T>(vec): vec を座標圧縮します。
• get(x): x の座標圧縮後の値を取得します。
• inv(x): x の座標圧縮前の値を取得します。
• getCompressed(): 座標圧縮後の配列を取得します。

計算量

• compress<T>(vec): $\mathrm{O}(N \log N)$
• get(x): $\mathrm{O}(\log N)$
• inv(x): $\mathrm{O}(1)$
• getCompressed(): $\mathrm{O}(N)$

Verified with

• test/library_checker/data_structure/area_of_union_of_rectangles.test.cpp
• test/library_checker/data_structure/associative_array.test.cpp
• test/library_checker/data_structure/point_add_rectangle_sum.test.cpp
• test/library_checker/data_structure/point_set_range_composite_large_array.test.cpp
• test/library_checker/data_structure/range_kth_smallest.test.cpp
• test/library_checker/data_structure/static_range_count_distinct.test.cpp
• test/library_checker/data_structure/static_range_frequency.test.cpp
• test/library_checker/data_structure/static_range_inversions_query.test.cpp
• test/library_checker/data_structure/static_range_mode_query.test.cpp

Code

#pragma once

/**
 * @brief Compression (座標圧縮)
 * @docs docs/others/compression.md
 */

#include <vector>
#include <algorithm>

template <typename T>
struct compress{
    std::vector<T> sorted;
    std::vector<int> compressed;

    compress(const std::vector<T> &vec){
        int n = vec.size();
        compressed.resize(n);
        for(T x : vec){
            sorted.emplace_back(x);
        }
        std::sort(sorted.begin(), sorted.end());
        sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
        for(int i = 0; i < n; ++i){
            compressed[i] = std::lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin();
        }
    }

    int get(const T &x) const{
        return std::lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    }

    T inv(const int x) const{
        return sorted[x];
    }

    size_t size() const{
        return sorted.size();
    }

    std::vector<int> getCompressed() const{
        return compressed;
    }
};

#line 2 "lib/others/compression.hpp"

/**
 * @brief Compression (座標圧縮)
 * @docs docs/others/compression.md
 */

#include <vector>
#include <algorithm>

template <typename T>
struct compress{
    std::vector<T> sorted;
    std::vector<int> compressed;

    compress(const std::vector<T> &vec){
        int n = vec.size();
        compressed.resize(n);
        for(T x : vec){
            sorted.emplace_back(x);
        }
        std::sort(sorted.begin(), sorted.end());
        sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
        for(int i = 0; i < n; ++i){
            compressed[i] = std::lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin();
        }
    }

    int get(const T &x) const{
        return std::lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    }

    T inv(const int x) const{
        return sorted[x];
    }

    size_t size() const{
        return sorted.size();
    }

    std::vector<int> getCompressed() const{
        return compressed;
    }
};

Back to top page