离散化是什么：一些数字，他们的范围很大（0-1e9），但是个数不算多（1-1e5），并且这些数本身的数字大小不重要，重要的是这些数字之间的相对大小（比如说某个数字是这些数字中的第几小，而与这个数字本身大小没有关系，要的是相对大小）（6 8 9 4 离散化后即为 2 3 4 1）（要理解相对大小的意思）（6在这4个数字中排第二小，那么就把6离散化成2，与数字6本身没有关系， 8,9,4亦是如此）（2018.3.26 对这篇博客进行补充修改，被一道题的离散化卡到了，花了一晚上时间，才找到BUG（需离散化的数字有无相同的数字），黑体字为今晚对此篇博客进行了补充完善与区别）

离散化思想：因为数字太大，导致没有办法开那么大的数组，又因为数字个数并不多，这时候就可以对它们进行离散化，离散化是改变了数字的相对大小，例如，有500000个数字，他们的范围是0-1e9的，这样就满足离散化的条件。

就比如说，你可以开一个5e5的数组，但是你不能开一个1e9的数组。只改变这些数字的相对大小

 

第一种离散化。（包含重复元素，并且相同元素离散化后也要相同，推荐使用）
离散化以前一直搞不懂是怎么实现的，看了一个代码才明白。


const int maxn=1e5+10;

int a[maxn], t[maxn];

int n;

scanf("%d",&n);

for(int i=1; i<=n; i++)

    scanf("%d",a[i]),t[i]=a[i];

sort(t+1,t+n+1);

m=unique(t+1,t+1+n)-t-1;//m为不重复的元素的个数

for(int i=1; i<=n; i++)

    a[i]=lower_bound(t+1,t+1+m,a[i])-t;

原来的a[i]离散化后成了后来的a[i]；

 

离散化后的a[i]范围是（1-m）；
举个栗子：
原序列：6 9 4 6 4
排序后：4 4 6 6 9
unique（元素去掉重复的）后：4 6 9 6 9  （前m位数字无重复，（自己瞎猜的：其他数字跟sort排序后的序列相比不改变 ） | 感谢薇亚040214同学提出疑问，为什么unique去重后是4,6,9,6,9，而不是4,6,9,4,9，我当时也百度了unique函数，我也觉得应该是4,6,9,4,9,最后敲了下面的代码，结果虽然是4,6,9,6,9，但是具体的解释我也说不清楚，哪位大牛懂的话，希望可以留言，2018.7.21更）


#include <cstdio>

#include <algorithm>

using namespace std;

int a[10]={6,9,4,6,4};

int main()

{

    int n=5;

    sort(a,a+n);//排序后4 4 6 6 9

    n=unique(a,a+n)-a;

    for(int i=0;i<5;i++)

        printf("%d ",a[i]);

    printf("\n");

    //最后输出4 6 9 6 9, 我猜是重复的只留一个，后面的数组没变，保留原来的数字

}


unique有一个返回值，例如有十个有序的数列3 3 5 5 6 6 6 7 7 8，不重复的数字有五个，使用unique去重之后数列变成了3 5 6 7 8 6 6 7 7 8，它只改变了前五个数字后边的不变，返回值是 最后一个改变的数字的地址。so：m=unique(t+1,t+1+n)-t-1;一般要减去首地址（t+1），m为不重复的数字的个数

 

  第二种离散化（复杂度低，1.包含重复元素，并且相同元素离散化后不相同，2.不包含重复元素，并且不同元素离散化后不同，符合这两种的其中一个，推荐使用  |   感谢Angel-Yan同学指出错误，2018.7.21更正）


struct A

{

    int x, idx;

    bool operator < (const A &rhs) const

    {

        return x < rhs.x;

    }//也可以写个cmp函数排序

};

A a[MAXN];

int rank[MAXN];

int n;

scanf("%d",&n);

for(int i = 1; i <= n; ++i)

{

    scanf("%d", &a[i].x);

    a[i].idx = i;

}

//for(int i=1; i<=n; i++)

//    printf("%d  %d\n",a[i].idx,a[i].x);

//printf("\n");

sort(a + 1, a + n + 1);

//for(int i=1; i<=n; i++)

//    printf("%d  %d\n",a[i].idx,a[i].x);

//printf("\n");

for(int i = 1; i <= n; ++i)

{

    rank[a[i].idx] = i;

//    printf("rank[%d] = %d\n",a[i].idx,i);

}

给你们个例子：
i      1 2 3 4
x     6 8 9 4
idx  1 2 3 4
排序后：

 

i      1 2 3 4  //离散化后的数字
x     4 6 8 9 
idx  4 1 2 3  //数字原来的所在的位置编号
将上面两行黑体数字对应起来 即是：rank[4]=1,rank[1]=2,rank[2]=3,rank[3]=4;  //rank[i]=j表示将原来在第i个位置上的数字离散化成j
so:
rank[1]=2;
rank[2]=3;
rank[3]=4;
rank[4]=1;
so:   6 8 9 4

就离散化为2，3，4，1
如果你想用原来的数字，就用排过序的结构体a[2]=6,a[3]=8,a[4]=9,a[1]=4; //a[i]=j表示排过序后现在的a数组里第i个数字的是j。j也就是第i小。
a[i]是原来的数字；
rank是离散化后的数字；