座標圧縮は頻出ですが、値の復元はなんとなく億劫になりがちなのでもろもろライブラリ化しました。

1 次元の場合

class Compress:
  def __init__(self, arr):
    values = sorted(set(arr))
    self.translator = dict([(values[i], i) for i in range(len(values))])
    self.inv_translator = values

  def to_comp(self, x):
    return self.translator[x]

  def from_comp(self, v):
    return self.inv_translator[v]

to_comp: arr に登場する値を入れると、圧縮後の値が返ってくる
from_comp: 圧縮後の値を入れると、対応する arr の値が返ってくる

点列の圧縮から、多次元座標列の圧縮に拡張することもできます。

2 次元の場合

class Compress2D:
  def __init__(self, arr):
    self.x = Compress([x for x, y in arr])
    self.y = Compress([y for x, y in arr])

  def to_comp(self, x):
    return (self.x.translator[x[0]], self.y.translator[x[1]])

  def from_comp(self, v):
    return (self.x.translator[v[0]], self.y.translator[v[1]])

2 次元座標列が与えられた時、それぞれの座標軸で圧縮を行います。

to_comp: arr に登場する座標を入れると、圧縮後の座標が返ってくる
from_comp: 圧縮後の座標を入れると、対応する arr の座標が返ってくる

例題

ネタバレ

二次元の座標圧縮を行う

https://atcoder.jp/contests/abc168/tasks/abc168_f

おわり

座標圧縮してセグ木に載せてまた戻すところまでをライブラリに