競プロノート

Appearance

座標圧縮（Coordinate Compression） ​

値の大小関係を保ったまま、0始まりの連続整数に変換するテクニック。

値が大きくても、異なる値の個数が少なければコンパクトに扱える。

特徴 ​

項目内容
用途座標の縮小・値の順位付け
前処理O(N log N)
圧縮O(log N)
復元O(1)
空間計算量O(N)

考え方 ​

値をソートして重複を除去し、各値をその位置に変換する。

例えば、

text
元の値 : 100 500 100 -20 300
圧縮後 :   1   3   1   0   2

大小関係と等しい値の関係は維持される。

実装 ​

cpp

#pragma once
#include <bits/stdc++.h>
using namespace std;

template<typename T = int>
struct CC {
    bool initialized = false;
    vector<T> xs;

    void add(T x) { xs.push_back(x); initialized = false; }

    void init() {
        if (initialized) return;
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        initialized = true;
    }

    // 登録済みの値を圧縮
    int operator()(T x) {
        if (!initialized) init();
        int i = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        assert(i < (int)xs.size() && xs[i] == x);
        return i;
    }

    // 圧縮前の値を取得
    T operator[](int i) {
        if (!initialized) init();
        assert(0 <= i && i < (int)xs.size());
        return xs[i];
    }

    int size() {
        if (!initialized) init();
        return (int)xs.size();
    }

    // x以下の最大座標の添え字（存在しなければ-1）
    int floor_index(T x) {
        if (!initialized) init();
        return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
    }
};

使用例 ​

cpp
vector<ll> a = {100, 500, 100, -20, 300};

CC<ll> cc;
for (ll x : a) cc.add(x);

// 圧縮
for (ll x : a) cout << cc(x) << ' ';
// 1 3 1 0 2

// 圧縮前の値
cout << cc[2] << '\n'; // 300

// 異なる値の個数
cout << cc.size() << '\n'; // 4

主な操作 ​

操作機能
add(x)値を登録
init()ソート・重複除去
cc(x)登録済みの値を圧縮
cc[i]圧縮前の値を取得
size()異なる値の個数
floor_index(x)x以下の最大座標の添え字

未登録の値について ​

cc(x) は登録済みの値に対して使用する。

一方、floor_index(x) は未登録の値でも利用できる。

cpp
CC<int> cc;
cc.add(10);
cc.add(30);
cc.add(50);

cc(30);          // 1
cc.floor_index(20); // 0
cc.floor_index(40); // 1
cc.floor_index(5);  // -1

floor_index(x) は「x以下で最大の登録済み値」の添え字を返す。

存在しなければ-1を返すので、配列アクセスには注意する。

典型的な応用 ​

  • 値が大きい配列の頻度管理
  • 転倒数
  • BIT・セグメント木との組み合わせ
  • 順位の管理
  • 2次元座標の圧縮

注意点 ​

  • 圧縮後も大小関係は維持される。
  • 元の値の差は維持されない。
  • 同じ値は同じ添え字になる。
  • cc(x) に渡す値は事前に登録する。
  • add() の後は必要に応じて自動で再初期化される。
  • 追加された値によって既存の圧縮添え字が変わることがある。
  • そのため、基本的にはすべての値を登録してから利用する。
  • xs を直接変更せず、add() を使用する。

関連 ​

  • lower_bound・upper_bound
  • BIT
  • セグメント木
  • 転倒数