Open Astral-23 opened 1 month ago
// Coodinate Compression // https://youtu.be/fR3W5IcBGLQ?t=8550
template <typename T> struct CC { bool initialized; vector<T> xs; T mx, Mx; CC(T mx, T Mx) : mx(mx), Mx(Mx) { initialized = false; } void add(T x, T width = 0) { for (T w = -width; w < 0; w++) if (x + w <= Mx && x >= mx - w) xs.push_back(x + w); for (T w = 0; w < width + 1; w++) if (x <= Mx - w && x + w >= mx) xs.push_back(x + w); } void add(vec<T> A, T width = 0) { for (T x : A) add(x, width); } void init() { sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); initialized = true; } int operator()(T x) {//以下最大のindex if (!initialized) init(); return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1; } T operator[](int i) { if (!initialized) init(); return xs[i]; } int size() { if (!initialized) init(); return xs.size(); } };
// Coodinate Compression // https://youtu.be/fR3W5IcBGLQ?t=8550