离散化 | FXJFXJ

1 如何实现离散化？

![[../../../images/Z-attachment/Pasted image 20231126151937.png]] ## 2 解析我们可以发现，最后归位后的数组就对应的是 \(Rank\) 的值，因此这道题就是去求出最后的数组。注意本题要去重，因此在离散化之前排序之后要去一遍重。

怎么用代码实现？这道题要有两个数组，一个原数组，设为 \(a\)。一个离散化归位数组，设为 \(d\)。输入时要将原数组同步到离散化数组上。

第一步没啥好说的，对原数组排序。

第二步之前要进行去重，我们可以用 STL 中的一个神奇的函数：\(Unique\)，STL 好闪，拜谢 STL，使用方法跟 \(Sort\) 函数一样，只不过没有第三个参数。

具体来说，这个函数可以去除数组中的相邻重复项，并返回指向最后一个前移覆盖位置的迭代器。因此想要完全去重就必须先排序。虽然说是去重，本质上其实是让后面的数覆盖掉重复的数。那么因此我们就可以利用这个函数对原数组进行去重并计算出去重后的个数。

去重后的个数会用到一行神奇的代码：\(unique (a+1, a+n+1)-(a+1)\)，就能求出去重的个数了，具体原理查百度，不是本题主要内容。

第二步根本就不用写代码，可以直接进第三步。

第三步也要用到一个函数：\(lower\_bound\) 形式是这样的：\(lower\_bound (first, last, val)\) 可以查找区间中第一个大于等于 \(Val\) 的值，返回指向这个数的下标的迭代器。因此这条语句就可以自动完成归位操作：\(d[i]=lower\_bound (a+1, a+n+1, d[i])-a\)。

3 代码

#include <bits/stdc++.h>
using namespace std;
int a[100005], d[100005]; //原数组和离散化数组
int main()
{
    ios::sync_with_stdio(0);
    int T, n;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            d[i] = a[i]; //同步原数组数据
        }
        sort(a + 1, a + n + 1);                       //第一步排序
        int cnt = unique(a + 1, a + n + 1) - (a + 1); //去重
        for (int i = 1; i <= n; i++)
            d[i] = lower_bound(a + 1, a + cnt + 1, d[i]) - a; //第三步归位
        for (int i = 1; i <= n; i++)
            cout << d[i] << " ";
        cout << endl;
    }
}