Compression
座標圧縮をする.
Spec
-
add(T x)
- 要素
x
を追加する
- 要素
-
build()
- 準備
-
comp(T x)
- 座圧した結果を返す
-
comp(vector<T> x)
- まとめて座圧
x = comp(std::move(x))
すると楽です.
Code
#include <vector>
template<class T>
struct Compression {
using size_type = std::size_t;
std::vector<T> v;
Compression(){}
void add(const T& t) { v.push_back(t); }
void build() {
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
}
size_type comp(const T& x) const {
return lower_bound(begin(v), end(v), x) - begin(v);
}
size_type size() const { return v.size(); }
};