!Сжатие координат

Сжатие координат - метод, помогающий в offline задачах с большими входными значениями. Мы просто сортируем координаты и обходим этот массив, попутно сопоставляя каждому новому значения наименьшее незадействованное число. Также, если координаты важны для некоторых подсчетов, то можно добавить обратное сопоставление, что позволит учесть их там, где они нам понадобятся. Автор обычно использует 2 map-a для двух биекций соответственно, но быстрее будет работать обычный массив.

Код

Украден с алгоритмики, но тем не менее

vector<long long> compress(vector<long long> a) {
  vector<long long> b = a;
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());
  for (long long &x : a) {
    x = (long long)(lower_bound(b.begin(), b.end(), x) - b.begin());
  }
  return a;
}