座標圧縮
座標圧縮は座標値の大小関係だけが問題になるときに、座標値をその大小の順番に置きかえるテクニックのこと。
具体的には数列
$ \{a_i\} = \{23, 2, 14, 51, 2\}
が与えられたときに、それを
$ \{2, 0, 1, 3, 0\}
のような数列に置き換える。これは二分探索を用いれば
$ O(N \log N)
で実行できる。