Compress
(data_structure/compress.hpp)

• View this file on GitHub
• Last update: 2023-11-14 21:20:53+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)$

Depends on

• テンプレート (template/template.hpp)

Required by

• offline 2D segtree (data_structure/offline_segtree_2d.hpp)

Verified with

• test/data_structure/Point_Add_Rectangle_Sum.test.cpp

Code

#pragma once

#include "../template/template.hpp"

namespace lib {

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];
    }
};

}

#line 2 "data_structure/compress.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "data_structure/compress.hpp"

namespace lib {

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];
    }
};

}

Back to top page