Compress
(data_structure/compress.hpp)

• View this file on GitHub
• Last update: 2024-02-25 23:03:04+09:00
• Include: #include "data_structure/compress.hpp"

説明

build()

座圧を実行する。 $O(N\log N)$

add(T val)

valを座圧の対象にする。 $O(1)$

get(T val)

valを座圧した後の値を返す。 $O(\log N)$

size()

座圧後の要素数を返す。 $O(1)$

find(T val)

valが座圧対象であるか判定。 $O(\log N)$

val(int idx)

座圧後の値がidxのものの座圧前の値を返す。 $O(1)$

Required by

• Area of Union of Rectangles (data_structure/area_of_union_of_rectangles.hpp)
• offline 2D dual segtree (data_structure/offline_dual_segtree_2d.hpp)
• offline 2D segtree (data_structure/offline_segtree_2d.hpp)
• Static Rectangle Sum (data_structure/static_rectangle_sum.hpp)
• Inversion Number (math/inversion_number.hpp)

Verified with

• test/data_structure/Area_of_Union_of_Rectangles.test.cpp
• test/data_structure/Point_Add_Rectangle_Sum.test.cpp
• test/data_structure/Rectangle_Add_Point_Get.test.cpp
• test/data_structure/Rectangle_Sum_Segtree.test.cpp
• test/data_structure/Static_Range_Inversion_Query.test.cpp
• test/data_structure/Static_Rectangle_Sum.test.cpp
• test/geometry/segment_intersection.test.cpp
• test/math/Inversion_Number.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <vector>

namespace ebi {

template <class T> struct compress {
  private:
    std::vector<T> cp;

  public:
    compress() = default;

    compress(std::vector<T> cp_) : cp(cp_) {
        build();
    }

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

    void add(const T &val) {
        cp.emplace_back(val);
    }

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

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

    bool find(const T &val) const {
        auto itr = std::lower_bound(cp.begin(), cp.end(), val);
        if (itr == cp.end())
            return false;
        else
            return *itr == val;
    }

    T val(int idx) const {
        assert(0 <= idx && idx < (int)cp.size());
        return cp[idx];
    }
};

}  // namespace ebi

#line 2 "data_structure/compress.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

namespace ebi {

template <class T> struct compress {
  private:
    std::vector<T> cp;

  public:
    compress() = default;

    compress(std::vector<T> cp_) : cp(cp_) {
        build();
    }

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

    void add(const T &val) {
        cp.emplace_back(val);
    }

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

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

    bool find(const T &val) const {
        auto itr = std::lower_bound(cp.begin(), cp.end(), val);
        if (itr == cp.end())
            return false;
        else
            return *itr == val;
    }

    T val(int idx) const {
        assert(0 <= idx && idx < (int)cp.size());
        return cp[idx];
    }
};

}  // namespace ebi

Back to top page