已解压暑假集训知识补充.pdf

离散化

•在某些问题中，点的坐标范围非常大，如

从-10^9到10^9，如果直接用线段树来处理，

空间和时间都难以承受。

•其中有些问题中，点的个数比较少，如只

有10^4个，直接用线段树会造成空间和时

间的浪费。这时就可以利用离散化。

离散化

•离散化的步骤：

•将所有点的坐标值排序，去掉相同的坐标

值（当n比较小时，可以使用set），然后对

应坐标值在排好序的下标，给原来的点赋

上新的坐标值。

•显然，离散化后的点顺序不变，但是之间

的距离发生了变化。这一点在处理长度等

问题时要注意。

POJ2528Mayorsposters

•题意：按顺序给定若干线段，先给出的线

段会被后面的线段覆盖，问最后不被完全

覆盖的线段有几条

•数据范围：

•1=n=10000

•1=li=ri=

POJ2528Mayorsposters

•这道题可以用线段树解决。先把直线置空，

按照逆序（从n到1）处理线段。

•如果一条线段覆盖的区间有空白，就把Ans

加一，将空白填上。最后的结果就是Ans。

POJ2528Mayorsposters

•显然，对于坐标值的范围而言，线段树有

点缓慢。

•注意到点的个数不多，可以采用离散化加

速。

•将区间的坐标离散化后，区间坐标的范围

只有1到20000，这时再采用线段树就快多

了。由于本题只需要计数，长度可以不必

考虑。

POJ2528Mayorsposters

•当然，这道题还有可以不用离散化+线段树

的方法。请大家自己思考。

POJ2528Mayorsposters

•当然，这道题还有可以不用离散化+线段树

的方法。请大家自己思考。