Banner 图源网络，侵删。

离散化

离散化：将无限空间中的有限个体映射到有限的空间中。

比如说我有一个无尽的坐标轴，上面有 $10^4$ 个点，每个点的坐标值可以很大很大接近无限。如果我想知道比其中一个点小的点有多少个，暴力比较每个点的坐标值则会因为数据过大而 Boom。而我们通过点与点相对关系，将点的值进行重新赋值，则可以大大减小算法的复杂度。

比如，我现在的数轴上只有6个点， 他们的坐标分别为 $0$、$610$、$10^5+2$、$99$、$5$、$10^9+45$，如果我只是按照他们原有的值进行比较，最大要比较到 $10^9+45$。而如果我们用他们的相对大小来进行比较，即转换为 $0$、$3$、$4$、$2$、$1$、$5$ 则会方便很多。这就是离散化的思想，就是将离散的事物进行重新分配。

离散化方法：排序+二分

（推荐使用本方法）

基本原理就是排序后使用STL中的unque()函数来获取整体数据不同元素的个数，然后在已排序序列二分查找 $num[i]$ 的值，从而得到对 $num[i]$ 对应的值，然后进行重新赋值。

for(int i = 0; i < n; i++){
    scanf("%d", &num[i]);
    disc[i] = num[i]; // num:原数据数组，disc:离散化后的数组
}
sort(disc, disc + n);
cnt = unique(disc, disc + n) - disc; // STL中的unique函数，具体内容见👇
for(int i = 0; i < n; i++)
    num[i] = lower_bound(disc, disc + n, num[i]) - disc;
  • unique(a, b)函数：STL中比较常见的函数，他的功能是“删除”序列中所有相邻的重复元素（只保留一个），因为只是处理相邻的重复元素所以在使用这个函数之前要进行排序。（此处略去更具体的都能再写一页博客的内容）。其中参数a,b为指针，类似sort()函数中的参数。
  • lower_bound(a, b, v)函数：二分查找返回a、b指针之间空间中大于等于 $v$ 的第一个迭代器。

离散化方法：排序+暴力

#include <bits/stdc++.h>
#define MAX_N 1e5+5  // 根据实际问题调整
struct Node{
    int data;
    int index;
}num[MAX_N];
bool cmp(Node a, Node b){
    return a.data < b.data;
}
int rank[MAX_N], n;
int main(){
    scanf("%d", &n);
    for(int i = 0;i < n; i++){
        scanf("%d", &num[i].data);
        num[i].index = i;
    }
    sort(num, num + n, cmp);
    for(int i = 1; i <= n; i++){
        rank[num[i].id] = i;
    }
    return 0;
}

排序之后按照原顺序进行赋值，相同元素就会出现离散化不成同一元素的情况，所以不推荐这种方法。

听大佬说洛谷P1955是一道有关离散化的题，我这个蒟蒻还没有做。🙃

有时间做了再搞题解什么的。🙃

题解我搞出来了，传送门：🚪