代码模板-离散化

const int N = 1e5 + 5;
int n, m;
int a[N], b[N]; // a[]为原数组，b[]是离散化后的数组，下标范围分别是 [1, n]，[1, m]

void init()
{
    sort(a + 1, a + 1 + n); // 先对数组排序
    m = 0;
    for (int i = 1; i <= n; i++)
        if (i == 1 || a[i] != a[i - 1])
            b[++m] = a[i];

    // 或STL: m = unique(a + 1, a + 1 + n) - a; 这种写法会丢失原数组
}

int query(int x)
{
    return lower_bound(b + 1, b + m + 1, x) - b;
}

// std::vector<int> arr;
std::vector<int> tmp(arr);  // tmp 是 arr 的一个副本
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
  arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();