坐标压缩的快速实现

[GoBigorGoHome]

坐标压缩可以分为两种：ordered 和 unordered。或者说保持顺序 和 不保持顺序。

我想研究一下坐标压缩的快速实现。第一步是看看别人是怎么写的。

maspy 的写法

#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UNIQUE(x) \
  sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

vc<int> key = A;
UNIQUE(key);
for (auto &x: A) x = LB(key, x);

我写的保持顺序的坐标压缩函数

// 坐标压缩
template<typename T>
std::vector<int> compress(const std::vector<T>& a) {
  int n = (int) a.size();
  std::vector<int> I(n);
  std::iota(I.begin(), I.end(), 0);
  std::sort(I.begin(), I.end(),
            [&a](int i, int j) { return a[i] < a[j]; });
  std::vector<int> order(n);
  for (int i = 1; i < n; i++)
    order[I[i]] = order[I[i - 1]] + (a[I[i - 1]] < a[I[i]]);
  return order;
}

// 坐标压缩并且unique
template<typename T>
std::vector<int> compress_unique(std::vector<T>& a) {
  int n = (int) a.size();
  std::vector<int> I(n);
  std::iota(I.begin(), I.end(), 0);
  std::sort(I.begin(), I.end(),
            [&a](int i, int j) { return a[i] < a[j]; });
  std::vector<int> order(n);
  std::vector<T> b(n);
  b[0] = a[I[0]];
  int j = 0;
  for (int i = 1; i < n; i++) {
    if (a[I[i - 1]] < a[I[i]])
      b[++j] = a[I[i]];
    order[I[i]] = j;
  }
  b.erase(b.begin() + j + 1, b.end());
  a = b;
  return order;
}