tools/compress.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "tools/compress.hpp"

Depends on

• tools/base.hpp

Code

#pragma once

#include "./base.hpp"

#include <algorithm>
#include <vector>

namespace matumoto {
  // verify:ABC036_C
  template <typename T>
  struct Compress {
    vector<T> xs;
    Compress() {}
    Compress(int N): xs(N, 0) {}
    Compress(const vector<T> &vs): xs(vs) {}

    void set(int i, T x) {
      xs[i] = x;
    }

    void set(const vector<T> &vs) {
      for (int i = 0; i < min<int>(xs.size(), vs.size()); i++) {
        xs[i] = vs[i];
      }
    }

    void add(T x) {
      xs.emplace_back(x);
    }

    void add(const vector<T> &vs) {
      for (const T &x: vs) {
        xs.emplace_back(x);
      }
    }

    Compress<T> build() {
      sort(xs.begin(), xs.end());
      xs.erase(unique(xs.begin(), xs.end()), xs.end());
      return *this;
    }

    vector<T> get(const vector<T> &vs) const {
      vector<T> res = vs;
      for (T &x: res) {
        x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
      }
      return res;
    }

    int get(T k) const {
      return lower_bound(xs.begin(), xs.end(), k) - xs.begin();
    }

    const T &operator[](int k) const {
      return xs[k];
    }
  };
} // namespace matumoto

#line 2 "tools/compress.hpp"

#line 2 "tools/base.hpp"

namespace matumoto {
  using namespace std;
}
#line 4 "tools/compress.hpp"

#include <algorithm>
#include <vector>

namespace matumoto {
  // verify:ABC036_C
  template <typename T>
  struct Compress {
    vector<T> xs;
    Compress() {}
    Compress(int N): xs(N, 0) {}
    Compress(const vector<T> &vs): xs(vs) {}

    void set(int i, T x) {
      xs[i] = x;
    }

    void set(const vector<T> &vs) {
      for (int i = 0; i < min<int>(xs.size(), vs.size()); i++) {
        xs[i] = vs[i];
      }
    }

    void add(T x) {
      xs.emplace_back(x);
    }

    void add(const vector<T> &vs) {
      for (const T &x: vs) {
        xs.emplace_back(x);
      }
    }

    Compress<T> build() {
      sort(xs.begin(), xs.end());
      xs.erase(unique(xs.begin(), xs.end()), xs.end());
      return *this;
    }

    vector<T> get(const vector<T> &vs) const {
      vector<T> res = vs;
      for (T &x: res) {
        x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
      }
      return res;
    }

    int get(T k) const {
      return lower_bound(xs.begin(), xs.end(), k) - xs.begin();
    }

    const T &operator[](int k) const {
      return xs[k];
    }
  };
} // namespace matumoto

Back to top page