坐标压缩与离散化

坐标压缩与离散化

简单版本

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
auto get = [&](int x) {return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
};

封装

template <typename T> struct Compress_ {int n, shift = 0; // shift 用于标记下标偏移量vector<T> alls;Compress_() {}Compress_(auto in) : alls(in) {init();}void add(T x) {alls.emplace_back(x);}template <typename... Args> void add(T x, Args... args) {add(x), add(args...);}void init() {alls.emplace_back(numeric_limits<T>::max());sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());this->n = alls.size();}int size() {return n;}int operator[](T x) { // 返回 x 元素的新下标return upper_bound(alls.begin(), alls.end(), x) - alls.begin() + shift;}T Get(int x) { // 根据新下标返回原来元素assert(x - shift < n);return x - shift < n ? alls[x - shift] : -1;}bool count(T x) { // 查找元素 x 是否存在return binary_search(alls.begin(), alls.end(), x);}friend auto &operator<< (ostream &o, const auto &j) {cout << "{";for (auto it : j.alls) {o << it << " ";}return o << "}";}
};
using Compress = Compress_<int>;