座標圧縮
(Src/Sequence/CompressedSequence.hpp)

View this file on GitHub
Last update: 2025-03-04 23:23:46+09:00
Include: #include "Src/Sequence/CompressedSequence.hpp"

概要

長さ $N$ の列 $A$ を座標圧縮して、これを管理します。 $A$ の要素の種類数を $M$ 、すなわち $\mid \{\ x \mid \exists i_{1\le i\le N}\ x = A_i\ \}\mid = M$ とします。

使い方

テンプレート引数T

圧縮する対象の $A$ はstd::vector<T>である必要があります。

制約: operator< と operator==が定義されている型・クラスであること(無いとコンパイルエラーになります)

コンストラクタ

(1) CompressedSequence() = default;
(2) CompressedSequence(const std::vector<T>& A)
(3) CompressedSequence(InputIterator first, InputIterator last)

(1) デフォルトコンストラクタ

(2) 引数に与えた $A$ で座標圧縮した列を構築します。

(3) イテレータfirst, last間で構築します。

計算量: $O(N\log N)$

size

inline usize size() const noexcept

$M$ を返します。

計算量: 定数時間

operator[]

u32 operator[](const T& v) const

集合 $\{\ x \mid \exists i_{1\le i\le N}\ x = A_i\ \}$ 上でvでlower_boundします。

lower_bound - begin()を返します。

計算量: $O(\log N)$

upper_bound

u32 upper_bound(const T& v) const

集合 $\{\ x \mid \exists i_{1\le i\le N}\ x = A_i\ \}$ 上でvでupper_boundします。

upper_bound - begin()を返します。

計算量: $O(\log N)$

at

u32 at(const T& v) const

operator[]と一緒ですが、 $v$ が $\{\ x \mid \exists i_{1\le i\le N}\ x = A_i\ \}$ に存在しない場合assertに引っかかる

contains

bool contains(const T& v) const

$v$ が含まれるか判定します。

計算量: $O(\log N)$

find

u32 find(const T& v) const

$v$ が含まれるなら(*self)[v]を、そうでないならCompressedSequence<T>::NotFoundを返します。

CompressedSequence<T>::NotFoundはstd::numeric_limits<u32>::max()と同じ値です。

計算量: $O(\log N)$

map

inline u32 map(u32 i) const noexcept

引数で与えた非負整数$i$ に対して、 $A_i$ の座標圧縮後の値を返します。

制約: $i\ <\ N$

計算量: 定数時間

inverse

inline T inverse(u32 i) const noexcept

集合 $\{\ x \mid \exists i_{1\le i\le N}\ x = A_i\ \}$ で $i$ 番目に小さい要素を返します。

制約: $0\ \le\ i\ <\ \text{size()}$

計算量: 定数時間

comped

inline std::vector<T> comped() const noexcept

集合 $\{\ x \mid \exists i_{1\le i\le N}\ x = A_i\ \}$ に属する値を小さい順に入れたvectorを返します。

計算量: 集合サイズ

アルゴリズム、そもそも座標圧縮とは

長さ $N$ の整数列 $B$ は、次の条件を満たす時に「 $A$ を座標圧縮した列」であると(私を含む多くの競プロerが)呼びます。

$B$ の各要素が $0$ 以上 $M$ 未満の整数である¹。
$A_i = A_j$ を満たす時、またその時に限り $B_i = B_j$ である。
$A_i < A_j$ を満たす時、またその時に限り $B_i < B_j$ である。

このような $B$ は $A$ に対して一意に定まることが知られています。

例1: $(3, 2, 15, 3, 13, 15)$ を座標圧縮した列は $(1, 0, 3, 1, 2, 3)$ です。

例2: $(0, 0, 0)$ を座標圧縮した列は $(0, 0, 0)$ です。

例3: トランプの役の列 $(\text{A}, \text{Q}, \text{4}, \text{2})$ を大小関係を「大富豪で強い方が大きい」と定めて座標圧縮した列は $(2, 1, 0, 3)$ です。

座標圧縮した列の構築のオーソドックスなやり方として、以下の $2$ つのやり方が有名です。

本質は $1$ も $2$ も同じです。

ソートして重複要素を取り除いた列を用意して、その列上で二分探索することで自身より小さい値の種類数を得る。
連想配列に $A$ を押し込んで、小さい順に番号を振る。

本ライブラリでは $1$ のやり方を採用しています。

$1$ 以上 $M$ 以下とする人もいると思います。0-indexedか1-indexedかの違いだけです。 ↩

Depends on

標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

Verified with

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <vector>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa

#line 2 "Src/Sequence/CompressedSequence.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/CompressedSequence.hpp"

#include <vector>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa

座標圧縮 (Src/Sequence/CompressedSequence.hpp)

概要

使い方

テンプレート引数T

コンストラクタ

size

operator[]

upper_bound

at

contains

find

map

inverse

comped

アルゴリズム、そもそも座標圧縮とは

Depends on

Required by

Verified with

Code

座標圧縮
(Src/Sequence/CompressedSequence.hpp)