説明

座標の大小関係を維持しつつ、値の範囲を座標の種類数に狭める。

計算量

  • build: $O(N \log N)$
  • get: $O(\log N)$

実装例

  • add(vs): vs内にある座標をすべて追加する
  • add(x): 座標 x を追加する
  • build(): 構築する
  • get(vs): vs内にある座標をそれぞれ座標圧縮したものを返す
  • get(x): 座標 x を座標圧縮したものを返す
  • [k]:= 座標圧縮後の k が示す実際の座標を返す
template< typename T >
struct Compress {
  vector< T > xs;

  Compress() = default;

  Compress(const vector< T > &vs) {
    add(vs);
  }

  Compress(const initializer_list< vector< T > > &vs) {
    for(auto &p : vs) add(p);
  }

  void add(const vector< T > &vs) {
    copy(begin(vs), end(vs), back_inserter(xs));
  }

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

  void build() {
    sort(begin(xs), end(xs));
    xs.erase(unique(begin(xs), end(xs)), end(xs));
  }

  vector< int > get(const vector< T > &vs) const {
    vector< int > ret;
    transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
      return lower_bound(begin(xs), end(xs), x) - begin(xs);
    });
    return ret;
  }

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

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

検証

AtCoder Beginner Contest 036 C - 座圧

int main() {
  int N;
  cin >> N;
  vector< int64 > A(N);
  cin >> A;
  Compress< int64 > comp(A);
  comp.build();
  for(auto &p : comp.get(A)) cout << p << "\n";
}