Library/Other/Compress.hpp

• View this file on GitHub
• Last update: 2026-02-12 16:49:49+09:00
• Include: #include "Library/Other/Compress.hpp"

Depends on

• Library/Common.hpp

Verified with

• verify/LC-RectangleSum.test.cpp

Code

#include "../Common.hpp"

template<typename T>
class Compress{
    public:
    Compress(vector<T> &A, bool unique_flag = true) : data_(A){
        sort(data_.begin(), data_.end());
        if(unique_flag) data_.erase(unique(data_.begin(), data_.end()), data_.end());
        n_ = (int)data_.size();
    }

    int Index(const T x) const {
        int ret = distance(data_.begin(), lower_bound(data_.begin(), data_.end(), x));
        assert(ret < n_ && data_[ret] == x);
        return ret;
    }

    int LowerBound(const T x) const {
        int ret = distance(data_.begin(), lower_bound(data_.begin(), data_.end(), x));
        return ret;
    }

    int UpperBound(const T x) const {
        int ret = distance(data_.begin(), upper_bound(data_.begin(), data_.end(), x));
        return ret;
    }

    size_t Size() const {
        return n_;
    }

    T operator[](const int k) const {
        return data_.at(k);
    }

    private:
    size_t n_;
    vector<T> data_;
};

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/Other/Compress.hpp"

template<typename T>
class Compress{
    public:
    Compress(vector<T> &A, bool unique_flag = true) : data_(A){
        sort(data_.begin(), data_.end());
        if(unique_flag) data_.erase(unique(data_.begin(), data_.end()), data_.end());
        n_ = (int)data_.size();
    }

    int Index(const T x) const {
        int ret = distance(data_.begin(), lower_bound(data_.begin(), data_.end(), x));
        assert(ret < n_ && data_[ret] == x);
        return ret;
    }

    int LowerBound(const T x) const {
        int ret = distance(data_.begin(), lower_bound(data_.begin(), data_.end(), x));
        return ret;
    }

    int UpperBound(const T x) const {
        int ret = distance(data_.begin(), upper_bound(data_.begin(), data_.end(), x));
        return ret;
    }

    size_t Size() const {
        return n_;
    }

    T operator[](const int k) const {
        return data_.at(k);
    }

    private:
    size_t n_;
    vector<T> data_;
};

Back to top page