CoordinateCompression

クラス · 座標圧縮

template <class T>
struct CoordinateCompression;

概要

座標圧縮

テンプレートパラメータ

名前	説明
`T`	座標の型

計算量

型宣言に実行時計算量はない

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空の座標圧縮器を構築する (2) 与えた列から座標圧縮器を構築する	(1) $O(1)$ (2) 要素数を $n$ として $O(n\log n)$

メンバ関数

名前	説明	計算量
`front`	最小の登録値を返す	$O(1)$
`back`	最大の登録値を返す	$O(1)$
`add`	build前の列へ値を追加する	償却 $O(1)$
`build`	登録値をソートして重複を除く	登録数を $n$ として $O(n\log n)$
`contains`	値が登録されているか返す	$O(\log n)$
`get`	登録された値の圧縮番号を返す	$O(\log n)$
`lower_bound`	値以上となる最初の圧縮番号を返す	$O(\log n)$
`upper_bound`	値より大きくなる最初の圧縮番号を返す	$O(\log n)$
`compress`	列の各値を圧縮番号へ変換する	入力長を $k$ として $O(k\log n)$
`size`	異なる登録値の個数を返す	$O(1)$

演算子

名前	説明	計算量
`operator[]`	圧縮後の番号から元の値を返す	$O(1)$

メンバの詳細

(constructor)

// (1)
CoordinateCompression() = default;

// (2)
CoordinateCompression(const std::vector<T> &_data);

(1) 空の座標圧縮器を構築する

計算量: $O(1)$

(2) 与えた列から座標圧縮器を構築する

パラメータ _data: 圧縮対象の列
計算量: 要素数を $n$ として $O(n\log n)$

get

int get(T x) const;

登録された値の圧縮番号を返す

x は登録済みでなければならない。未登録の値を含む境界を扱うなら lower_bound / upper_bound を使う。

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

lower_bound

int lower_bound(T x) const;

値以上となる最初の圧縮番号を返す

x は登録済みでなくてよい。半開区間の左端に使う。

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

upper_bound

int upper_bound(T x) const;

値より大きくなる最初の圧縮番号を返す

x は登録済みでなくてよい。閉区間の右端に使う。

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

compress

std::vector<int> compress(const std::vector<T> &v) const;

列の各値を圧縮番号へ変換する

各要素は登録済みでなければならない。

計算量: 入力長を $k$ として $O(k\log n)$