这几天在做线段树的专题，不免遇到一些题，数据很大，如果直接建树，会造成内存超出限制，这时就要进行离散化了。
如果是区间的离散化，一般区间会涉及覆盖关系， 那么运用离散化之后，区间的覆盖关系不能变，例如：
1——10 ，2——7 ，3——11,6——22；
将坐标从小到大排序，也就是1,2,3,6,7,10,11,22
那么新的区间也就是
1——6
2——5
3——7
4——8
覆盖关系没变，但是值小了很多，瞬间就减少了内存消耗
int seg[maxn][2];//保存原来的点
struct node
{
int p;
int line;
}mat[maxn<<1]
for(.....)
{
scanf(".....");
mat[i<<1].line=-(i+1);
mat[i<<1|1].line=(i+1);
mat[i<<1].p=seg[i][0];
mat[i<<1|1].p=seg[i][1];
}
sort(mat,mat+2*n,cmp);
for(.....)
{
if(temp!=seg[i].p)//防止相同端点映射到不同的点,temp是上一个点
{
ans++;
temp=seg[i].p;
}
if(mat[i].line<0) //左边,line 存的就是第i+1条边
seg[-mat[i].line-1][0]=ans;//离散这条边的左端
else
seg[mat[i].line-1][1]=ans;//离散这条边的右端
}
这样的话，离散前的点是没了，如果我们不需要离散前的点，那么可以这么做，如果需要的话，可以开数组保存下来或者用map，把离散前的坐标当成key，离散化的做value。这样即离散了坐标，也保留了原坐标
离散化适用于处于数据极大时的情况，例如应用在线段树上。